Реферат: Титов Д. В., Кобак В. Г. Анализ подходов к улучшению результатов работы генетического алгоритма при решении однородной минимаксной задачи. // Проблемы информатики в образовании, управлении, экономике и технике: Сб

Титов Д.В., Кобак В.Г. Анализ подходов к улучшению результатов работы генетического алгоритма при решении однородной минимаксной задачи. // Проблемы информатики в образовании, управлении, экономике и технике: Сб. статей Всерос. научно-техн. конф.– Пенза: ПДЗ, 2008. – С. 76-78.

АНАЛИЗ ПОДХОДОВ К УЛУЧШЕНИЮ
РЕЗУЛЬТАТОВ РАБОТЫ ГЕНЕТИЧЕСКОГО АЛГОРИТМА
ПРИ РЕШЕНИИ ОДНОРОДНОЙ МИНИМАКСНОЙ ЗАДАЧИ

Д.В. Титов, В.Г. Кобак

Донской государственный технический университет,
г. Ростов-на-Дону

В настоящее время непрерывно расширяется сфера применения многопроцессорных вычислительных систем обработки данных, охватывая все новые области в различных отраслях науки, бизнеса и производства. Для повышения эффективности решения задач на данных системах применяются алгоритмы распределения задач по параллельно работающим устройствам.

В случае однородных вычислительных систем следует составить расписание для n однородных параллельных процессоров, на которые необходимо распределить m независимых заданий, образующих параллельную программу. Математическая постановка данной задачи приведена в [1], где отмечено, что при больших значениях m и n время нахождения оптимального решения очень сильно возрастает и начиная с определенных размеров не может быть получено за определенное время. Для нахождения решения за разумные временные рамки при условии, что решение может быть близким к оптимальному, применяются приближенные эвристические методы.

Одними из самых популярных эвристических методов являются генетические алгоритмы (ГА). ГА являются одной из парадигм эволюционных вычислений, представляют собой алгоритмы поиска лучшего, а не оптимального решения задачи, построены на принципах, сходных с принципами естественного отбора и генетики. Общий принцип работы ГА состоит в следующем [2]: на первом шаге формируется начальное поколение, состоящее из заданного числа особей; на втором шаге происходит отбор особей для применения ГА операторов кроссовера и мутации с заданной вероятностью и формирование нового поколения; на шаге три происходит проверка условия останова, которая обычно заключается в неизменности лучшего решения в течение заданного числа поколений; если проверка прошла успешно, то лучшая особь выбирается как найденное решение, иначе происходит переход на второй шаг. В базовой схеме работы ГА выбор родительской пары для оператора кроссовера заключается в том, что берется очередная особь и случайным образом выбранная особь из исходного вектора особей. Для формирования нового поколения используется турнирный отбор для результирующей особи и случайно выбранной особи.

В данной работе предложено две модификации базовой схеме работы ГА. Первая модификация заключается в изменении выбора родительской пары для оператора кроссовера, которая заключается в использовании в качестве оператора выбора бинарного турнирного отбора [3]. Во второй модификации предложено внести изменение в формирование нового поколения, которое заключается в том, что в турнирном отборе будут участвовать очередная особь и результирующая, полученная в ходе выполнения операторов кроссовера и мутации.

Для сравнения предложенных модификаций с базовой схемой работы ГА был проведен вычислительный эксперимент. В ходе эксперимента были случайным образом созданы по 100 векторов загрузок в диапазоне [25, 30], количество процессоров задавалось в диапазоне [2, 4], а число работ менялось в диапазоне [25, 30]. Для ГА параметры были взяты следующие: число особей составляло 50, условие останова – 500 поколений, вероятность кроссовера – 90%, вероятность мутации – 10%. Полученные результаты усреднялись по количеству экспериментов и приведены в сводной таблице.


Количество процессоров, n

Количество задач, m

Усредненное значение критерия

Усредненное время решения задач , мс

Базовая схема ГА

Модификация выбора родительской пары

Модификация формирования нового поколения

Базовая схема ГА

Модификация выбора родительской пары

Модификация формирования нового поколения

2

25

348

348

344

18

18

19

26

357

357

357

18

18

17

27

375

375

371

19

19

20

28

385

385

385

19

19

18

29

402

402

398

21

21

22

30

413

413

413

20

20

20

3

25

240

240

235

18

18

19

26

245

245

242

19

19

21

27

248

248

247

19

19

19

28

267

267

262

20

20

21

29

272

272

269

20

20

22

30

277

277

275

21

21

21

4

25

185

185

182

19

19

19

26

189

189

187

20

20

20

27

192

192

190

20

20

20

28

196

196

193

20

19

21

29

213

213

209

22

22

23

30

217

217

215

22

22

24


Таким образом, проанализировав результаты, приведенные в сводной таблице, можно отметить, что самой эффективной является модификация формирования нового поколения, которая выдает результат, практически всегда лучший по сравнению с базовой схемой ГА и модификацией выбора родительской пары для оператора кроссовера. Базовая схема ГА и модификация выбора родительской пары в среднем ничем не отличаются друг от друга как по точности, так и по времени решения. Среднее время работы предложенных алгоритмов очень быстрое и практически соизмеримо друг с другом и не превышает нескольких десятков миллисекунд.

Библиографический список

1. Кобак, В.Г., Титов, Д.В. Анализ работы алгоритма Романовского с использованием разных подходов к формированию верхней и нижней границ // Сб. тр. МНК ММТТ-20. – Т.2. – Ярославль: ЯГТУ, 2007.

2. Кобак, В.Г., Будиловский, Д.М. Генетический подход к решению минимаксной задачи в однородных системах обработки информации // Сб. тр. МНК ММТТ-19. – Т.2. – Воронеж: ВГТА, 2006.

3. Кобак, В.Г., Будиловский, Д.М. Сравнительный анализ приближенных алгоритмов решения минимаксной задачи для однородных приборов // Вестник ДГТУ. – 2006. – Т.6. – №4.