Программные реализации оператора проектирования на эпсилон-симплекс::Журнал СА 12.2014
www.samag.ru
     
Поиск   
              
 www.samag.ru    Web  0 товаров , сумма 0 руб.
E-mail
Пароль  
 Запомнить меня
Регистрация | Забыли пароль?
Журнал "Системный администратор"
Журнал «БИТ»
Наука и технологии
Подписка
Где купить
Авторам
Рекламодателям
Магазин
Архив номеров
Вакансии
Контакты
   

  Опросы
1001 и 1 книга  
12.02.2021г.
Просмотров: 7488
Комментарии: 0
Коротко о корпусе. Как выбрать системный блок под конкретные задачи

 Читать далее...

11.02.2021г.
Просмотров: 7880
Комментарии: 0
Василий Севостьянов: «Как безболезненно перейти с одного продукта на другой»

 Читать далее...

20.12.2019г.
Просмотров: 14668
Комментарии: 0
Dr.Web: всё под контролем

 Читать далее...

04.12.2019г.
Просмотров: 14407
Комментарии: 12
Особенности сертификаций по этичному хакингу

 Читать далее...

28.05.2019г.
Просмотров: 15670
Комментарии: 2
Анализ вредоносных программ

 Читать далее...

Друзья сайта  

Форум системных администраторов  

sysadmins.ru

 Программные реализации оператора проектирования на эпсилон-симплекс

Архив номеров / 2014 / Выпуск №12 (145) / Программные реализации оператора проектирования на эпсилон-симплекс

Рубрика: Наука и технологии

Без фото ТКАЧЕНКО К.С., инженер 1-й кат., аспирант, ассистент, tkachenkokirillstanislavovich@mail.ru, tkachenkokirillstanislavovich@gmail.com

Программные реализации оператора проектирования на эпсилон-симплекс

Рассматривается несколько различных программных реализаций оператора проектирования на ε-симплекс. Приводятся необходимые формулы, таблицы

В общем виде задача разработки и исследования программных реализаций оператора проектирования на ε-симплекс (πεN) актуальна и своевременна, при этом связана с важными научными и практическими задачами построения средств поддержки принятия решений (СППР), автоматизированных систем управления технологическими процессами (АСУ ТП), оптимизации и автоматизации производственных процессов, управления распределенными, облачными, вычислительными системами, сетями и средами, построения программных систем (ПС). В последних исследованиях и публикациях, в которых начинают решать данную проблему и на которые опирается автор [1-8], описывается решение различных задач с использованием проекционных и беспроекционных алгоритмов стохастической аппроксимации. При этом в работе [1] приводятся алгоритм и программная реализация на языке Фортран-IV оператора πεN. Нерешенной прежде частью общей проблемы, которой посвящена эта статья, является реализация оператора πεN на нескольких различных языках программирования высокого уровня (ЯП ВУ) с учетом разных подходов.

Цель данной работы – разработка и исследование программных систем, реализующих оператор πεN.

Известно [1], что рандомизированные стратегии, лежащие в основе стохастических автоматов, используют рекуррентные правила вида:

pn+1 = Rn(x1,..., xn; p1,..., pn; ξ1,..., ξn), n = 1, 2,...,                               (1)

В выраженни (1):

  • pn – вектор условных вероятностей выбора вариантов
    x(1),..., x(N) в момент времени tn,
  • Rn – вектор-функция движения со значениями в симплексе SεN.

Когда происходит выбор очередного варианта xn+1, рассчитываются значения вероятностей выбора вариантов pn+1 по (1). Удобно выбор результирующего варианта осуществлять методом деления отрезка.

Для удобства используются обозначения как в [1, 2], а именно:

Формула 1;

Формула 2;

Формула 3,

если X = {x(1),..., x(N)}; ω – элементарный исход.

Пусть для любого q ∈ RN вектор-столбец p = πεN{q}, принадлежащий (N-1)-мерному единичному ε-симплексу:

Формула 4                         (2)

определяется условием:

Формула 5.

Для любого q ∈ RN вектор πεN{q} существует и единственен и q = πεN{q} тогда и только тогда, когда q ∈ SεN.

Известны эффективные алгоритмы адаптивного выбора вариантов [1], которые можно подразделить на беспроекционные алгоритмы адаптивного выбора вариантов вида pn+1 = pn - γnR(xn, pn, ξn) и проекционные алгоритмы адаптивного выбора вариантов вида Формула 6, где:

  • R(xn, pn, ξn) = Rn – вектор движения алгоритма,
  • γn > 0 – скалярный множитель – длина шага,
  • n = 1, 2,... – номер шага,
  • εn ∈ [0, N-1) – параметр проектора Формула 7 (3) на n-ом шаге.

Проекционные алгоритмы могут быть лучше беспроекционных, поскольку их можно использовать для решения более широкого класса задач (как с бинарными, так и с небинарными потерями ξn за счет обеспечения нормировки использованием оператора проектирования).

При разработке СППР можно произвести сравнение различных реализаций оператора πεN на различных ЯП ВУ. Поскольку в основе СППР и моделей различных сетей и систем будут лежать методы и алгоритмы, использующие оператор πεN, то это сравнение позволит в дальнейшем производить выбор и обоснование используемых сред разработки и ЯП ВУ, в том числе и методом анализа иерархий (МАИ), и производить структурный синтез результирующих систем.

Алгоритм выполняется следующей последовательностью шагов [1]:

Шаг 0: k := 0, q0 := 0.

Шаг i.1: Производится проецирование вектора qi-1 на SN-k.

Шаг i.2: Если πN-k{qi-1} ∈ SN-k, то конец.

Шаг i.3: Иначе исключаются из рассмотрения все отрицательные k компонентов, i := i + 1, qi := πN-k{qi-1}, переход к шагу i.1.

Результаты разработки сводятся в таблицу 1. При этом в различных реализациях могут как использоваться, так и не использоваться возможности ЯП ВУ для абстракции списков (list comprehension, LC) – компактные описания операций обработки списков.

Таблица 1. Разработанные программные системы, реализующие оператор πεN

Обозначение Использованный ЯП ВУ Используются возможности спискового включения (абстракция списков, list comprehension) Комментарий
1. P1 Python Да Для представления исключенных из рассмотрения значений вектора используется «None»
2. P2 Python Да Для представления исключенных из рассмотрения значений вектора используется «NaN»
3. E1 Erlang Нет Используются возможности списковых функций ЯП ВУ
4. E2 Erlang Да
5. J1 Java Нет Используется кодирование алгоритма, близкое к реализации [1]
6. J2 Java Близкие возможности

Соответствующие фрагменты исходных кодов приводятся в листингах 1-7.

Листинг 1. Исходный код P1

def defined(q):

return [x for x in q if x is not None]

 

def sq1(q):

return 1.0 - sum(defined(q))

 

def countOfDefined(q):

return float(len(defined(q)))

 

def proek(q, eps):

ar = 1.0 - eps * len(q)

p = [((x - eps) / ar) for x in q]

workIsDone = False

while not workIsDone:

workIsDone = True

cod = countOfDefined(p)

sq1p = sq1(p)

p2 = [((x + (sq1p / cod)) if (x is not None) else None) for x in p]

p = [(None if ((x is not None) and (x < 0.0)) else x) for x in p2]

workIsDone = (p == p2)

return [(eps + ar * (x if x is not None else 0.0)) for x in p]

 

if __name__ == '__main__':

print(proek([1, 2, 3, 4, 5, 6, 5, 4, 3, 2, 1], 0.001))

 

Листинг 2. Исходный код P2

import math

def defined(q):

return [x for x in q if not math.isnan(x)]

 

def sq1(q):

return 1.0 - math.fsum(defined(q))

 

def countOfDefined(q):

return float(len(defined(q)))

 

def proek(q, eps):

nan = float('nan')

ar = 1.0 - eps * len(q)

p = [((x - eps) / ar) for x in q]

workIsDone = False

while not workIsDone:

cod = countOfDefined(p)

sq1p = sq1(p)

p2 = [(x + (sq1p / cod)) for x in p]

p = [(nan if x < 0.0 else x) for x in p2]

workIsDone = (p == p2)

return [(eps + ar * (x if not math.isnan(x) else 0.0)) for x in p]

 

if __name__ == '__main__':

print(proek([1, 2, 3, 4, 5, 6, 5, 4, 3, 2, 1], 0.001))

 

Листинг 3. Исходный код E1

-module(proek).

-export([main/0, main/1, proek/2]).

 

main() -> main(args).

main(_) -> run().

 

run() ->

io:format("~p\n", [proek([1, 2, 3, 4, 5, 6, 5, 4, 3, 2, 1], 0.001)]).

 

proek(Q, Eps) ->

AR = 1.0 - Eps * length(Q),

P1 = lists:map(fun(X) -> (X - Eps) / AR end, Q),

P2 = proekNaPolnySimplex(P1),

lists:map(fun(X) -> Eps + AR * X end, P2).

 

proekNaPolnySimplex(Q) ->

P1 = lists:map(fun(X) ->

if

X =/= nil -> X + sq1(Q) / countOfDefined(Q);

true -> X

end

end, Q),

P2 = lists:map(fun(X) ->

if

X < 0 -> nil;

true -> X

end

end, P1),

case countOfDefined(P1) =/= countOfDefined(P2) of

true ->

proekNaPolnySimplex(P2);

false ->

lists:map(fun(X) ->

if

X =/= nil -> X;

true -> 0

end

end, P2)

end.

sq1(Q) -> 1 - lists:sum(lists:filter(fun(X) -> (X =/= nil) end, Q)).

 

countOfDefined(Q) -> length(lists:filter(fun(X) -> (X =/= nil) end, Q)).

 

Листинг 4. Исходный код E2

-module(proek2).

-export([main/0, main/1, proek/2]).

 

main() -> main(args).

main(_) -> run().

 

run() ->

io:format("~p\n", [proek([1, 2, 3, 4, 5, 6, 5, 4, 3, 2, 1], 0.001)]).

 

proek(Q, Eps) ->

AR = 1.0 - Eps * length(Q),

P1 = [(X - Eps) / AR || X <- Q],

P2 = proekNaPolnySimplex(P1),

[Eps + AR * X || X <- P2].

 

proekNaPolnySimplex(Q) ->

P1 = [if

X =/= nil -> X + sq1(Q) / countOfDefined(Q);

true -> X

end || X <- Q],

P2 = [if

X < 0 -> nil;

true -> X

end || X <- P1],

case countOfDefined(P1) =/= countOfDefined(P2) of

true ->

proekNaPolnySimplex(P2);

false ->

[if

X =/= nil -> X;

true -> 0

end || X <- P2]

end.

defined(Q) -> [X || X <- Q, X =/= nil].%lists:filter(fun(X) -> (X =/= nil) end, Q).

sq1(Q) -> 1 - lists:sum(defined(Q)).

countOfDefined(Q) -> length(defined(Q)).

 

Листинг 5. Исходный код J1

public class Main {

 

public static double[] proekNazinPoznyak(double[] q, double e) {

int N = q.length; // размерность вектора q

double r = e * N; // εN

double ar = 1.0 - r; // 1 - εN

double ak = N;

double sq1 = 0.0; // = 1 - ε{q_i}

 

double[] p = new double[N]; // результат

boolean[] mon = new boolean[N];

boolean shagAlgo = true;

 

for (int i = 0; i < N; i++) {

sq1 += q[i];

p[i] = q[i];

}

sq1 = 1 - sq1;

 

for (int i = 0; i < N; i++) {

mon[i] = false;

p[i] = (p[i] - e) / ar;

}

 

sq1 /= ar;

 

while (shagAlgo) {

shagAlgo = false;

 

for (int i = 0; i < N; i++) {

if (!mon[i]) {

p[i] += sq1 / ak;

}

}

 

for (int i = 0; i < N; i++) {

if (!mon[i] && (p[i] < 0.0)) {

sq1 = p[i];

p[i] = 0.0;

mon[i] = true;

ak--;

shagAlgo = true;

break;

}

}

}

 

for (int i = 0; i < N; i++) {

p[i] = ar * p[i] + e;

}

 

return p;

} // proekNazinPoznyak

 

public static void main(String[] args) {

double[] p = proekNazinPoznyak(new double[] { 1, 2, 3, 4, 5, 6, 5, 4, 3, 2, 1 }, 0.001);

for (double x : p)

System.out.println(" " + x);

}

}

 

Листинг 6. Исходный код J2

public class ProekWithLists {

 

private static double nil = Double.NaN;

 

private static boolean isNil(double x) {

return Double.isNaN(x);

}

 

public static double[] proekWithLists(double[] q, double eps) {

boolean workIsDone;

double[] p = new double[q.length];

double ar = 1.0 - eps * q.length;

for (int i = 0; i < q.length; i++) {

p[i] = (q[i] - eps) / ar;

}

do {

workIsDone = true;

double cod = countOfDefined(p);

double sq1p = sq1(p);

for (int i = 0; i < p.length; i++) {

if (!isNil(p[i])) {

p[i] += sq1p / cod;

}

}

for (int i = 0; i < p.length; i++) {

if (p[i] < 0.0) {

p[i] = nil;

workIsDone = false;

}

}

} while (!workIsDone);

for (int i = 0; i < p.length; i++) {

if (isNil(p[i])) {

p[i] = 0.0;

}

p[i] = eps + ar * p[i];

}

return p;

}

private static double[] defined(double[] q) {

java.util.ArrayList<Double> result = new java.util.ArrayList<Double>();

for (double y : q) {

if (!isNil(y)) {

result.add(y);

}

}

double[] resultArr = new double[result.size()];

for (int i = 0; i < result.size(); i++) {

resultArr[i] = result.get(i);

}

return resultArr;

}

 

private static double sq1(double[] q) {

double sum = 0;

for (double y : defined(q)) {

sum += y;

}

return 1 - sum;

}

private static int countOfDefined(double[] q) {

return defined(q).length;

}

}

 

Листинг 7. Исходный код J2, продолжение

public class Main {

public static void main(String[] args) {

double[] result = ProekWithLists.proekWithLists(new double[] { 1, 2, 3, 4, 5, 6, 5, 4, 3, 2, 1 }, 0.001);

for (double x : result) {

System.out.print(" " + x);

}

System.out.println();

}

}

Оценки метрических характеристик разработанных ПС, полученные с использованием программного обеспечения с открытым исходным кодом, сводятся в таблицу 2.

Таблица 2. Полученные метрические характеристики разработанных ПС

Н LOC L S F C C/F
1. P1 20 25 20 4 15 3,8
2. P2 21 27 21 4 13 3,3
3. E1 37 44 27 7 15 2,1
4. E2 32 40 21 8 16 2,0
5. J1 50 84 35 2 12 6,0
6. J2 60 67 35 5 17 3,4

В таблице используются обозначения:

  • Н – название реализации алгоритма;
  • LOC – количество строк кода;
  • L – количество строк;
  • S – количество операторов;
  • F – количество функций;
  • C – цикломатическая сложность программы по МакКейбу;
  • C/F – отношение C к F.

Выбор подходящей системы производится следующим образом. Пусть P = {P1, P2, J1, J2, E1, E2,}. Тогда для оценки реализаций ПС по критериям LOC и C/F можно решить оптимизационную задачу:

Формула 8 (3)

Для (3) искомым является piopt = P2.

Вывод. В данной работе приведены результаты разработки и исследования программных систем, реализующих оператор πεN. Перспективой дальнейших изысканий по данной проблеме станут разработка и исследование оператора πεN на некоторых других ЯП ВУ и низкого уровня.

  1. Назин А.В. Адаптивный выбор вариантов: Рекуррентные алгоритмы/А.В. Назин, А.С. Позняк. – М.: «Наука», 1986. – 288 с.
  2. Назин А.В. О повышении эффективности автоматных алгоритмов адаптивного выбора вариантов/А.В. Назин//Адаптация и обучение в системах управления и принятия решений. – Новосибирск: «Наука», 1982. – С. 40-46.
  3. Ткаченко К.С. Управление качеством обслуживания в распределенной среде GLOBUS как в IT-инфраструктуре критического применения/К.С. Ткаченко, Н.Л. Корепанова//Системы контроля окружающей среды: сб. науч. тр., НАН Украины, МГИ. Вып.19/2013. – Севастополь, 2013. – С.97-100.
  4. Ткаченко К.С. Проекционный алгоритм стохастической аппроксимации с использованием соседних вариантов для оптимизации управления выбором управляющих воздействий/К.С. Ткаченко//Збірник наукових праць Кіровоградського національного технічного університету/Техніка в сільськогосподарському виробництві, галузеве машинобудування, автоматизація/. – Вип. 26. – Кіровоград: КНТУ, 2013. – С. 301-305.
  5. Ткаченко К.С. Исследование процессов управления распределенными средами проекционным алгоритмом стохастической аппроксимации/К.С. Ткаченко//Вестник СевНТУ: сб. науч. тр. Вып. 146/2014. Серия: Автоматизация процессов и управление. – Севастополь, 2014. – 244 с. – С. 36-39.
  6. Скаткова Н.А. Гарантоспособные технологии реконфигурации автоматизированных транспортно-производственных систем/Н.А. Скаткова//Радіоелектронні і комп'ютерні системи. Вип. 6. – Харьков, 2008. – С. 52-57.
  7. Воронин Д.Ю. Обеспечение высокой терминальной готовности на основе информационных технологий распределения ресурсов/Д.Ю. Воронин//Вісник СевНТУ: зб. наук. пр. Вип. 114/2011. Серія: Інформатика, електроніка, зв'язок. – Севастополь, 2011. – С. 100-105.
  8. Ткаченко К.С. Адаптивное принятие решений автоматными алгоритмами по критерию минимума предельных средних потерь/ К.С. Ткаченко//Вісник СевНТУ: зб. наук. пр. Вип. 149/2014. Серія: Інформатика, електроніка, зв'язок. – Севастополь, 2014. – 108 с. – С. 12-15.

Ключевые слова: программные системы, оператор проектирования.


Software implementations of the projection operator on the epsilon-simplex

Tkachenko Kirill Stanislavovich, 1st cat. Engineer, graduate student, assistant, tkachenkokirillstanislavovich@mail.ru, tkachenkokirillstanislavovich@gmail.com

Abstract

There are a number of different software implementations of the projection operator on the ε-simplex in this article. The necessary formulas, tables are provided.

Keywords: software systems, projection operator.


Комментарии отсутствуют

Добавить комментарий

Комментарии могут оставлять только зарегистрированные пользователи

               Copyright © Системный администратор

Яндекс.Метрика
Tel.: (499) 277-12-41
Fax: (499) 277-12-45
E-mail: sa@samag.ru