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

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

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

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

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

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

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

p_n+1 = R_n(x₁,..., x_n; p₁,..., p_n; ξ₁,..., ξ_n), n = 1, 2,...,                               (1)

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

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

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

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

;

;

,

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

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

                         (2)

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

.

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

Известны эффективные алгоритмы адаптивного выбора вариантов [1], которые можно подразделить на беспроекционные алгоритмы адаптивного выбора вариантов вида p_n+1 = p_n - γ_nR(x_n, p_n, ξ_n) и проекционные алгоритмы адаптивного выбора вариантов вида , где:

• R(x_n, p_n, ξ_n) = R_n – вектор движения алгоритма,
• γ_n > 0 – скалярный множитель – длина шага,
• n = 1, 2,... – номер шага,
• ε_n ∈ [0, N^-1) – параметр проектора  (3) на n-ом шаге.

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

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

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

Шаг 0: k := 0, q⁰ := 0.

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

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

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

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

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

Соответствующие фрагменты исходных кодов приводятся в листингах 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 – отношение C к F.

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

 (3)

Для (3) искомым является p_i^opt = 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.

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