Асимптотический вероятностный генетический алгоритм решения сложных задач глобальной оптимизации тема диссертации и автореферата по ВАК РФ 05.13.01, кандидат технических наук Галушин, Павел Викторович

• Галушин, Павел Викторович
• кандидат технических наук
• 2012

Оглавление диссертации кандидат технических наук Галушин, Павел Викторович

Содержание

Содержание

Введение

1 Асимптотический вероятностный генетический алгоритм псевдо-булевой оптимизации

1.1 Обзор существующих методов глобальной оптимизации

1.2 Асимптотическая мутация

1.3 Асимптотическая селекция

Выводы и результаты

2 Обобщения асимптотического вероятностного генетического алгоритма

2.1 Асимптотическая турнирная селекция

2.2 АВГА и ВГА для оптимизации функций целочисленных

(не бинарных) переменных

2.3 Учёт взаимосвязей между переменными в АВГА

Выводы и результаты

3 Программная реализация предложенных методов

3.1 Программная система «Асимптотический вероятностный генетический алгоритм»

3.2 Программная система «Глобальная оптимизация локальными и эволюционными многоагентными стохастическими алгоритмами (GOLEM-SA)»

3.3 Тестирование алгоритмов, не учитывающих взаимосвязи переменных

3.4 Тестирование алгоритмов, учитывающих взаимосвязи

переменных

Выводы и результаты

4 Эвристические алгоритмы динамического составления

расписаний

4.1 Динамическое составление расписаний

4.2 Применение рыночного алгоритма для управления цехом окраски грузовиков

4.3 Применение рыночного алгоритма для управления &1ГО-системой

Выводы

Заключение

Список литературы

Список публикаций автора

Введение диссертации (часть автореферата) на тему «Асимптотический вероятностный генетический алгоритм решения сложных задач глобальной оптимизации»

Введение

Актуальность. Задачи оптимизации постоянно возникают в деятельности человека, в частности, при проектировании технических и социально-экономических систем: если существует возможность выбора параметров такой системы, то их следует выбрать оптимальным с точки зрения цели функционирования системы образом. Классические методы оптимизации накладывают существенные ограничения на целевую функцию задачи оптимизации: выпуклость, аналитическое задание функции и возможность вычисления вектора градиента в любой допустимой точке.

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

Важным классом методов оптимизации, способных решать такие задачи оптимизации являются эволюционные алгоритмы и, в частности, генетические алгоритмы (ГА), основанные на имитации эволюционных процессов, происходящих в природе.

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

Однако существующие эволюционные методы оптимизации имеют большое количество настраиваемых параметров, что затрудняет их использование специалистами в прикладных областях, не являющимися экспертами в эволюционных методах оптимизации. Ситуацию ещё более усугубляет использование биологической терминологии при описании эволюционных алгоритмов — специалист, применяющий эволюционный алгоритм оптимизации для решения задачи в своей предметной области, должен обладать знаниями ещё в двух областях — теории эволюции и эволюционных методах оптимизации. Кроме того, многие эволюционные алгоритмы (в частности, генетический алгоритм) определены так, что их программные реализации оказываются плохо приспособленными для современных ЭВМ (с конвейерной архитектурой и аппаратной многопоточностью).

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

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

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

2. Предложить модификации существующих эволюционных алгоритмов, превосходящие существующие по быстродействию и эффективности.

3. Реализовать разработанные методы в виде программных систем.

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

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

Научная новизна результатов диссертационной работы состоит в следующем:

1. Предложен новый асимптотический вероятностный генетический алгоритм (АВГА) псевдо-булевой оптимизации, превосходящий известные аналоги (ГА, ВГА и другие) по быстродействию и эффективности использования аппаратных средств ЭВМ, но не уступающий им по надёжности решения задач оптимизации.

2. Предложен новый способ учёта взаимосвязи между переменными, позволяющий повысить эффективность вероятностного и асимптотического вероятностного генетических алгоритмов.

3. Предложены модификации ГА, ВГА и АВГА, позволяющие эффективно решать задачи оптимизации с целочисленными (не бинарными) переменными.

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

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

Практическая значимость. Разработанные в ходе исследования алгоритмы реализованы в виде программ «Асимптотический вероятностный генетический алгоритм (АРСА)» и «Глобальная оптимизация локальными и эволюционными многоагентными

стохастическими алгоритмами (GOLEM-SA)», прошедших государственную регистрацию (№2012612374, №2011611158). Данные программные системы позволяют пользователям, не являющимся экспертами в эволюционной оптимизации, эффективно решать сложные практические задачи глобальной оптимизации. Они прошли апробацию на ряде практических задач и продемонстрировали превосходство над существующими аналогами по надёжности и быстродействию.

Реализация результатов работы. Результаты работы вошли в отчёты по НИР № 2.1.1./2710 «Математическое моделирование инвестиционного развития региональных экономических систем» АВЦП «Развитие научного потенциала высшей школы (2009-2010 годы)», НК-136П/3 «Автоматизированная система решения сложных задач глобальной оптимизации многоагентными стохастическими алгоритмами» по направлению «Обработка, хранение, передача и защита информации» в рамках мероприятия 1.2.2 и НК-409П/49 «Разработка устойчивого гибридного генетического алгоритма для определения кристаллических структур химических соединений из данных порошковой дифракции» по направлению «Физические методы исследования химических соединений» в рамках мероприятия 1.2.1 Федеральной целевой программы «Научные и научно-педагогические кадры инновационной России на 2009-2013 годы».

В 2011 году по результатам исследования диссертанту присуждена Государственная премия Красноярского края в области системного анализа.

Основные защищаемые положения:

1. Разработанный асимптотический вероятностный генетический алгоритм (АВГА) псевдо-булевой оптимизации превосходит наиболее часто используемые эволюционные алгоритмы оптимизации по эффективности, быстродействию и затратам памяти.

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

3. Учёт взаимосвязи переменных задачи оптимизации в ВГА и АВГА позволяет повысить эффективность этих алгоритмов.

4. Предложенный асимптотический вероятностный генетический алгоритм позволяет эффективно решать задачу настройки параметров рыночного алгоритма динамического составления расписаний.

5. Регуляризация функции предложения позволяет повысить эффективность рыночного алгоритма динамического составления расписаний.

Публикации. По теме диссертации опубликовано тринадцать работ, в том числе пять в изданиях, входящих в перечень ведущих рецензируемых научных журналов и изданий, в которых должны быть опубликованы основные научные результаты диссертаций на соискание учёной степени доктора и кандидата наук, утверждённый Высшей аттестационной комиссией.

Апробация результатов работы. Результаты работы были представлены на Всероссийской научно-практической конференции «Актуальные проблемы авиации и космонавтики» (Красноярск, СибГАУ, 2005 г.), Международных научно-практических конференциях «Решетнёвские чтения» (Красноярск, СибГАУ, 2005, 2006 и 2009 гг.), на 11-й Международной конференции «Natural Computations» в Шанхае (КНР, 2011 г.), на Международных конференциях «Distributed Computing and Artificial Intelligence» и «Hybrid Artificial Intelligence Systems» в Саламанке (Испания, 2012 г.).

Структура работы. Диссертация содержит 95 страниц основного текста и состоит из введения, четырёх глав, заключения, списка литературы на 140 источников. Основной текст диссертации включает 8 таблиц, 15 рисунков.

Заключение диссертации по теме «Системный анализ, управление и обработка информации (по отраслям)», Галушин, Павел Викторович

Выводы

По результатам численных экспериментов можно сделать следующие выводы:

1. Предложенные алгоритмы глобальной оптимизации (в частности, асимптотический вероятностный генетический алгоритм с учётом зависимостей между переменными) эффективны при решении задачи настройки параметров рыночного алгоритма динамического составления расписаний.

2. Предложенная модификация рыночного алгоритма динамического составления расписаний позволяет уменьшить время выполнения поступающих в систему заявок.

Рыночный алгоритм может быть использован для решения задачи управления СИГО-системой в условиях неопределённости.

Заключение

При проведении диссертационного исследования получены следующие результаты:

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

2. Предложен новый асимптотический вероятностный генетический алгоритм псевдо-булевой оптимизации (АВГА), превосходящий распространённые аналоги: последовательное гюпуляционное обучение (РВ1Ь) по надёжности решения задач оптимизации, а генетический алгоритм (ГА) и вероятностный генетический алгоритм (ВГА) по быстродействию и надёжности решения задач оптимизации.

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

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

5. Предложены модификации ВГА и АВГА с целочисленным (небинарным) кодированием переменных, позволяющие решать задачи дискретной оптимизации без выполнения операции декодирования.

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

7. Проведён сравнительный анализ эффективности и быстродействия существующих и предложенных методов оптимизации при решении стандартных тестовых задач оптимизации. Полученные данные показывают, что предложенные методы оптимизации превосходят существующие по надёжности (все аналоги) и быстродействию (все аналоги, кроме метода РВ1Ь).

8. Проведён сравнительный анализ эффективности и быстродействия существующих и предложенных методов при решении сложной практической задачи оптимизации: задачи настройки параметров эвристических алгоритмов динамического составления расписания (для управления цехом окраски автомобилей и управления СШБ-системой). Полученные данные показывают, что предложенный асимптотический вероятностный генетический алгоритм не уступает широко распространённому Байесовскому алгоритму оптимизации и превосходит другие существующие методы по эффективности решения данной задачи.

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

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

Список литературы диссертационного исследования кандидат технических наук Галушин, Павел Викторович, 2012 год

Литература

[1] Айвазян, СА. Прикладная статистика: Основы моделирования и первичная обработка данных. Справочное изд. / С.А. Айвазян, И.С. Ешоков, Л.Д. Мешалкин; под ред. С. А. Айвазяна. — М.: Финансы и статистика, 1983. — 471 с.

[2] Айвязан, С.А. Прикладная статистика: Исследование зависимостей: Справ, изд. / С.А. Айвазян, И.С. Ешоков, Л.Д. Мешалкин; под ред. С А. Айвазяна. —■ М. Финансы и статистика, 1985. — 487 с.

[3] Антамошкин, А.Н. Оптимизация функционалов с булевыми переменными: научное издание / А.Н. Антамошкин ; ред. Л.А. Растригин. - Томск : Издательство Томского университета, 1987. -104 с.

[4] Аптон, Г. Анализ таблиц сопряжённости. — М.: Финансы и статистика, 1982.

[5] Бахвалов, Н.С. Численные методы / Н.С. Бахвалов, Н.П. Жидков, Г.М. Кобельков. — 3-е изд., доп. и перераб. — А/1.: БИНОМ. Лаборатория знаний, 2004. — 636 е., ил.

[6] Гринченко, С.Н., Алгоритм матричного случайного поиска / С.Н. Гринченко, Л.А. Растригин. — Пробл. случайного поиска (Рига), 1976, вып. 5, с. 167-184.

[7] Гринченко, С.Н. О матричном случайном поиске / С.Н. Гринченко, Л.А. Растригин. — Автоматика и вычисл. техника, 1976, № 1, с. 48—51.

[8] Гринченко, С.Н. Случайный поиск как адекватный аппарат описания механизмов функционирования нервной клетки / С.Н. Гринченко, С.Л. Загускин. — Вопр. кибернетики, вып. 45. Случайный поиск в

задачах оптимизации. М., Научный совет АН СССР по комплексной проблеме «Кибернетика», 1978, с. 124—134.

[9] Гринченко, С.Н., К вопросу о моделировании биологических процессов биосферы на основе иерархии алгоритмов случайного поиска / С.Н. Гринченко, C.J1. Загускин. — В кн.: Проблемы биосферы. Информационные материалы. Вып. 2. М., Научный совет АН СССР по проблемам биосферы, 1981, с. 136—142.

[10] Грэхем, Р. Конкретная математика. Основание информатики: Пер. с англ. / Р. Грэхем, Д.Э. Кнут, О. Паташник — М.: Мир, 1998. — 703 е., ил.

[11] Калинников, Ю.С. О некоторых модификациях алгоритма глобального статистического поиска по направляющей сфере / Ю.С. Калинников, A.JI. Лифшиц. — В кн.: Задачи статистической оптимизации. Рига, Зинатне. 1971. с. 197—202.

[12] Катковник, В.Я. Фильтрация и сглаживание функций многих переменных для целей поиска глобального экстремума / В.Я. Катковник, Г.Е. Антонов. — Автоматика и вычисл. техника, 1970, № 4, с. 32-38.

[13] Кнут, Д.Э. Искусство программирования, том 2. Получисленные алгоритмы / Д. Э. Кнут. - 3-е изд.: Пер. с англ. М.: ООО «И. Д. Вильяме», 2007. - 832 е.: ил.

[14] Кнут, Д.Э. Искус ство программирования, том 4, выпуск 2. Генерация всех кортежей и перестановок / Д. Э. Кнут. — Пер. с англ. - М.: ООО «И. Д. Вильяме», 2008. - 160 е.: ил.

[15] Коплиеи, Дж. Мультипарадигмениое проектирования для С++. Библиотека программиста. / Дж. Коплиен. — СПб.: Питер, 2005. — 235 е.: ил.

[16] Медведев, A.B. Непараметрические системы адаптации / A.B.

Медведев. — Новосибирск: Наука, 1983. — 174 с.

[17] Моцкус, И.Б. Многоэкстремальные задачи в проектировании / И.Б. Моцкус. — М.: Наука, 1967. - 214 с.

[18] Перегудов, Ф.И. Основы системного анализа: Учеб. 2-е. изд., доп. / Ф.И. Перегудов, Ф.П. Тарасенко — Томск: НТЛ, 1997. — 396 е.: ил.

[19] Петерсен, И. Статистическая оптимизация посредством сглаживания / И. Петерсен. — Изв. АН СССР. Техн. кибернетика, 1969, № 2, с. 36-44.

[20] Пиявский, С.А. Один алгоритм отыскания абсолютного экстремума функции / С.А. Пиявский // Журнал вычислительной математики и математической физики. — № 12. — 1972.

[21] Растригин, JI.A. Адаптация сложных систем / Л.А. Растригии. — Рига: Зинатне, 1981. — 375 с.

[22] Рао, С.Р. Линейные статистические методы и их применения. Пер. с англ. — М.: Наука, 1968. — 548 с.

[23] Рубан, А.И. Глобальная оптимизация методом усреднения координат: Монография / А.И. Рубан. — Красноярск: ИПЦ КГТУ, 2004. - 302 с.

[24] Семёнкин, Е.С. Вероятностные эволюционные алгоритмы оптимизации сложных систем / Е.С. Семенкин, Е.А. Сопов // Труды Международных научно-технических конференций «Интеллектуальные системы» (AIS'05) и «Интеллектуальные САПР»(CAD-2005): в 3 т. М.: ФИЗМАТЛИТ, 2005. Т. 1. 452 с.

[25] Семёнкин, Е.С. Методы оптимизации в управлении сложными системами : Учеб. пособие / Е.С. Семенкин, О.Э. Семёнкина, В.А. Терсков. Красноярск: Сиб. юрид. ин-т МВД России, — 2000.

[26] Страус ::труп, Б. Язык программирования Сн—г / Б. Страуструп. — Специальное издание. Пер. с англ. — М.: ООО «Бином-пресс», 2007. - 1104 е.: ил.

[27] Тынченко, B.C. Формирование распределённых систем структурного-параметрического синтеза нейросетвых моделей: дисс. на соиск. учен. степ, к.т.н. / B.C. Тынченко. — Красноярск: СибГАУ, 2008. - 165 с.

[28] Цыпкин, Я.З. Сглаженные рандомизированные функционалы в теории адаптации и обучения / Я.З. Цыпкин. — Автоматика и телемеханика. — 1971, №8, с,29-50.

[29] Уоррен, Г.С. Алгоритмические трюки для программистов / Г.С. Уоррен.: Пер. с англ. — М.: Издательский дом «Вильяме», 2007. — 288 е.: ил. — Парал. тит. англ.

[30] Aarts, E.H.L. Simulated Annealing: Theory and Applications / E.H.L. Aarts, P.J.M. van Laarhoven // London, Kluwer, 1987.

[31] Abdollahzadeh, A. Estimation of distribution algorithms applied to history matching / A. Abdollahzadeh, A. Reynolds, M. Christie, D. Corne, G. Williams, B. Davies // SPE Reservoir Simulation Symposium, Houston, Texas, U.S.A., 2011, paper 141161.

[32] Abdollahzadeh, A. Bayesian optimization algorithm applied to uncertainty quantification / A. Abdollahzadeh, A. Reynolds, M. Christie, D. Corne, B. Davies, G. Williams // SPE EUROPEC/EAGE Annual Conf. and Exhibition, Vienna, Austria, 2011, paper 143290.

[33] Adams, J. GEFE: Genetic к Evolutionary Feature Extraction for Periocular Based Biometric Recognition / J. Adams, D.L. Woodard, G. Dozier, P. Miller, G. Glenn, K. Bryant // Proceedings 2010 ACM Southeast Conference, April 15-17, 2010, Oxford, MS.

[34] Abu-Mahfouz, I. Parameter estimation of the Duffing oscillator using Poincare map and an elitist genetic algorithm / I. Abu-Mahfouz, A. Banerjee // Proc. ANNIE Conference, St. Louis, MI, Nov 1-3, 2010.

[35] Akay, B. Parameter tuning for the artificial bee colony algorithm / B. Akay, D. Karaboga // ICCCI 2009 (R. Kowalczyk N.T. Nguyen and S.-M. Chen, eds.), LNAI, vol. 5796, 2009, pp. 608-619.

[36] Babb, B. Improved Satellite Image Compression and Reconstruction via Genetic Algorithms / B. Babb, F. Moore, M. R. Peterson, G. Lamont // Electro-Optical Remote Sensing, Photonic Technologies, and Applications II, SPIE Symp. Optics/Photonics in Security k Defence, Cardiff, UK, 9/15-18, 2008.

[37] Badics, T. Approximation of some Nonlinear Binary Optimization Problems / T. Badics // Ph.D. Thesis, RUTCOR, Rutgers University, 1996.

[38] Baluja, S. Population-based Incremental Learning: A Method for Integrating Genetic Search Based Function Optimization and Competitive Leaning / S. Beluja // Tech. Report. No. CMU-CS-94-163, Carnegie Mellon University, 1994.

[39] Baluja, S. Removing the Genetics from the Standard Genetic Algorithm / S. Baluja, R. Caruana. — Morgan Kaufmann Publishers, pp. 38-46, 1995.

[40] Barahona, F. An application of combinatorial optimization to statistical physics and circuit layout design / F. Barahona, M. Grotschel, M. Jiinger, G. Reinelt // Operation Research 36 (1988), 493-513.

[41] Bonabeu, E. Swarm intellegence: from natural to artificial systems / E. Bonabeu, M. Dorigo, G. Theraulaz Oxford, UK: Oxford University Press, 1999.

[42] Bengoetxea E. EDA-PSO: A hybrid paradigm combining estimation of distribution algorithms and particle swarm optimization / E. Bengoetxea, P. Larranaga // Proc. of the 7th Int. Conf. on Swarm Intelligence (ANTS'10), ser. Lecture Notes in Computer Science, no. 6234, 2010, pp. 416-423.

[43] Boros, E. Optimal Cell Flipping to Minimize Channel Density in VLSI Design and Pseudo-Boolean Optimization / E. Boros, P.L. Hammer, M. Minoux, D. Rader // Discrete Applied Mathematics, 90 (1999) pp. 69-88.

[44] Boros, E. Pseudo-boolean optimization / E. Boros, P. L. Hammer // . Discrete Appl. Math., 123:155-225, 2002.

[45] Brest, J. Self-adapting control parameters in differential evolution: A comparative study on numerical benchmark problems / J. Brest, S. Greiner, B. Boscovic, M. Mernik, V. Zumer // IEEE Transactions on Evolutionary Computation, vol. 10, pp. 646-657, Dec 2006.

[46] Cario, M.C. Modeling and generating random vectors with arbitrary marginal distributions and correlation matrix / M. C. Cario, B. L. Nelson // Technical Report, Department of Industrial Engineering and Management Sciences, Northwestern University, Evanston, Illinois, 1997.

[47] Cavarettam, M.J. Data mining using genetic programming: The implications of parsimony on generalization error / M. J. Cavaretta, K. Chellapilla // Proceedings of the Congress on Evolutionary Computation, vol. 2. IEEE Press, 2009, pp. 1330-1337.

[48] Chou, J.H. Genetic algorithm in structural damage detection / J.H. Chou and J. Ghaboussi // Computers and Structures, 2001, 79(14), pp. 1335-1353.

[49] Clearwater, S.H. Thermal markets for controlling building environments / S. H. Clearwater, B. A. Huberman. // Energy Eng. 1994.91 P. 26-56.

[50] Coelho, L.S. Nonlinear model identification of an experimental ball-and-tube system using a genetic programming approach / L. S. Coelho, M. W. Pessoa // Mechanical Engineering and Signal Processing 23, 1434-1446, 2009.

[51] Coia, C. Automatic evolution of conceptual building architectures / C. Coia // Master's thesis, Department of Computer Science, Brock University. — 2011.

[52] Color ni, A. Distributed Optimization by Ant Colonies / A. Colorni, M. Dorigo et V. Maniezzo // Actes de la première conférence européenne sur la vie artificielle. — Paris, France: Elsevier Publishing, 1991. — pp. 134-142.

[53] De Simone, С. Exact ground states of Ising spin glasses: New experimental results with a branch and cut algorithm / C. De Simone, M. Diehl, M. Jünger P. Mutzel, G. Reinelt, G., Rinaldi // Journal of Statistical Physics 80 (1995) pp. 487-496.

[54] Documentation // Boost С f Libraries, 1998, URL: http://www.boost.org/doc/ (дата обращения 10.04.2012).

[55] Documentation // wxWidgets: Cross-platform GUI Library, 1992, URL: http://wxwidgets.org/docs/ (дата обращения 10.04.2012).

[56] Dozier, G. A Comparison of Two Genetic and Evolutionary Feature Selection Strategies for Periocular-Based Biometrie Recognition via XTOOLSS / G. Dozier, J. Adams, D.L. Woodard, P. Miller, K. Bryant // Proceedings of the 2010 International Conference on Genetic and Evolutionary Methods (GEM'10) Las Vegas, USA. - 2010.

[57] Espejo, P. A survey on the application of genetic programming to classification / P. Espejo, S. Ventura, F. Herrera // Systems, Man, and Cybernetics, Part C: Applications and Reviews, IEEE Transactions on, vol. 40, no. 2, pp. 121-144, 2010.

[58] Evtushenko, Yu.G. Recent Advances in Global Optimization / Yu.G. Evtushenko, M.A. Potapov, V.V. Korotkich // Prinston, Princeton University Press, 274-297, 1992.

[59] Farnsworth, M. A Novel Approach to Multi-level Evolutionary Design Optimization of a MEMS Device / M. Farnsworth, E. Benkhelifa, A. Tiwari, M. Zhu // Evolvable Systems: From Biology to Hardware, LNCS, vol 6274, pp 322-334. — 2010.

[60] Finck, S. Real-Parameter Black-Box Optimization Benchmarking 2010: Presentation of the Noiseless Functions / S. Finck, N. Hansen, R. Ros, A. Auger // Black-box Optimization Benchmarking, 2010, URL: http://coco. Iri.fr/BBOB-downloads/downloadlO. 2/bbobdocfunctions.pdf (дата обращения 10.04.2012).

[61] Foster, I. The Anatomy of the Grid: Enabling Scalable Virtual Organizations / I. Foster, C. Kesselman, S. Tuecke // International Journal of High Performance Computing Applications. - 2001. - 15(3). - P. 200-222.

[62] Fraenkel, A.S. Pseudo-Boolean functions and their graphs / A.S. Fraenkel, P.L. Hammer. // Annals of Discrete Mathematics 20 (1984), 137-146.

[63] Goldberg, D.E. Genetic algorithms in search, optimization, and machine learning / D.E. Goldberg. — Reading, MA: Addison-Wesley, 1989.

[64] Goldberg, D.E. A comparative analysis of selection schemes used in genetic algorithms / D. E. Goldberg, K. Deb. — Foundations of Genetic Algorithms, p. 69-93. — 1991.

[65] Gomez, S. The Tunneling Method Applied to Global Optimization / S. Gomez, A. V. Levy // SIAM, Numerical Optimization (Boggs, P.T., ed.), 213-244, 1985.

[66] Le Grand, S. The application of the genetic algorithm to the minimization of potential energy functions / S. Le Grand, K. Merz Jr. // J. Global Optirn., vol. 3, no. 1, pp. 49-66, 1993.

[67] Gupta, J.N.D. Comparing backpropagation with a genetic algorithm for neural network training / J.N.D. Gupta, R.S. Sexton // Omega, vol. 27, no. 6, pp. 684-679, 1999. URL: http://clx.doi.org/10.1016/S0305-0483(99)00027-4.

[68] Hammer, P.L. Plant location — a pseudo-Boolean approach / P.L. Hammer // Israel Journal of Technology 6 (1968), 330-332.

[69] Hammer, P.L. Pseudo-Boolean remarks on balanced graphs / P.L. Hammer // International Series of Numerical Mathematics 36, 69-78. — 1977.

[70] Hammer, P.L. Applications of pseudo-Boolean methods to economic problems / P.L. Hammer, and E. Shliffer // Theory and Decision 1, 296-308. — 1971.

[71] Han, K.-H. Quantum-inspired evolutionary algorithm for a class of combinatorial optimization / K.-H. Han, J.-H. Kim // IEEE Transactions on Evolutionary Computation 6, 580-593, 2002.

[72] Hansen, E.R. Global Optimization Using Interval Analysis / E.R. Hansen // New York, Marcel Dekker, 1992.

[73] Hansen, N. Real-Parameter Black-Box Optimization Benchmarking BBOB-2010: Experimental Setup / N. Hansen, A. Auger, S. Finck, R. Ros // Black-Box Optimization Benchmarking (BBOB), 2010, URL: http://coco.gforge.inria.fr/doku.php?id=bbob-2010-downloads (дата обращения 10.04.2012).

[74] Hillier, F.S. The evaluation of risky interrelated investments / F.S. Hiller /,/ North- Holland, Amsterdam, 1969.

[75] Hornung, C.A. Commentary and debate on Hunter's article on the validity of measures of association (with reply by the author). — Amer. J. Soc. 80, 975-1002, 1975.

[76] Huang C.L. GA-based feature selection and parameters optimization for support vector machines / C.L. Huang, C.-J. Wang // Expert Systems with Applications. Vol. 31(2), pp 231-240. — 2006.

[77] Huberman, B.A. Distributed computation as economic system / B.A. Huberman, T. Hogg. // J. Econom. Perspect. 1995.9 P. 141-152.

[78] Hunter, A.A. On the validity of measures of associations: the nominal-nominal, two-by-two case / A.A. Hunter // Amer. J. Soc., 79, 99-109, 1974.

[79] Jang, J.-S. Face detection using quantuminspired evolutionary algorithm / J.-S. Jang, K.-H. Han, J.-H. Kim // Proc IEEE Congress on Evolutionary Computation, Portland (OR), 2004.

[80] Karaboga, D. An Idea Based On Honey Bee Swarm for Numerical Optimization / D. Karaboga // Technical R,eport-TR06, Erciyes University, Engineering Faculty, Computer Engineering Department, 2005.

[81] Karp, R.M. Reducibility among combinatorial problems, In: Complexity of Computer Computation / R.M. Karp // pp. 85-104. R.G. Miller and J.W. Thatcher (eds.), Plenum Press, New York, 1972.

[82] Kennedy, J. Particle Swarm Optimization / J. Kennedy, R. Eberhart // Proceedings of IEEE International Conference on Neural Networks. IV. pp. 1942-1948, 1995.

[83] Kennedy, J. A Discrete Binary Version of the Particle Swarm Algorithm / J. Kennedy, R. C. Eberhart // In Proceedings of IEEE Conference on Systems, Man, and Cybernetics, Piscataway, New Jersey, USA, 1997.

[84] Kurose, J.F. A microeconomic approach to optimal resource allocation in distributed computer systems / J. F. Kurose, R. Simha. // IEEE Trans. Computers. 1989.38. P.707-717.

[85] Larranaga, P. Estimation of Distribution Algorithms. A New Tool for Evolutionary Computation / P. Larranaga, J.A. Lozano // Kluwer Academic Publishers, 2002.

[86] Laughhunn, D.J. Quadratic binary programming with applications to capital budgeting problems / D.J. Laughhunn // Operations Research 18 (1970), 454-461.

[87] Laughhunn, D.J. and D.E. Peterson. Computational experience with capital expenditure programming models under risk / D.J. Laughhunn, D.E. Peterson. // J. Business Finance 3 (1971), 43-48.

[88] Li, X. A Novel Estimation of Distribution Algorithm Using Graph-based Chromosome Representation and Reinforcement Learning / X. Li, B. Li, S. Mabu, K. Hirasawa // Proc. of IEEE Congress on Evolutionary Computation, 2011, pp. 37-44.

[89] Lima, H. A new design of genetic algorithm for bin packing / H. Lima, T. Yakawa // Evolutionary Computation, 2003. The 2003 Congresson Evolutionary Computation, 2:1044-1049, 2003.

[90] Liu, J. On setting the control parameter of the differential evolution method // J. Liu, J. Lampien in Proc. 8th Int, Conf. Soft Computing (MENDEL 2002), 2002, pp. 11-18.

[91] Lu, C. Hybrid Back-Propagation/Genetic Algorithm for Multilayer Feedforward Neural Networks / C. Lu, B. Shi // in Proceedings of ICSP2000, 2000, pp. 0-3.

[92] Main Page // Code::Blocks, 2005, URL: http://www.codeblocks.org/ (дата обращения 10.04.2012).

[93] Maimer, R. Genetic algorithms for protein tertiary structure prediction / R. Manner, B. Manderick // Parallel Problem Solving from Nature II, 1998, vol. 682, ch. 24, pp. 379-393.

[94] Manos, S. Evolutionary Design of Single-Mode Microstructured Polymer Optical Fibres using an Artificial Embryogeny Representation / S. Manos, M.C.J. Large, L. Poladian. // in Late Breaking Papers in the Genetic and Evolutionary Computation Conference July 7-11 2007, London 2007.

[95] Marano, G.C. Genetic algorithms in mechanical systems identification: State-of-the-art review / G. C. Marano, G. Quaranta, G. Monti // В. H. V. Topping, Y. Tsompanakis (Eds.), Soft Computing in Civil and Structural Engineering. — Stirlingshire (Scotland): Saxe-Coburg Publications, 2009.

[96] Metropolis, N. Equation of State Calculations by Fast Computing Machines / N. Metropolis, A. Rosenbluth, M. Rosenbluth, A. Teller, E. Teller. // J. Chem. Phys. Vol. 21, No. 6, 1087-1092, 1953.

[97] Moderes, H. Parameter identification of chaotic dynamic systems through an improved particle swarm optimization / H. Moderes, A. Alfi, M.-M. Fateh // Expert Systems with Applications 37, 3714-3720, 2010.

[98] Mohamad Ayob, A.F. An Optimization Framework for the Design of Planing Craft / A.F. Mohamad Ayob, T. Ray, W. Smith. // In International Conference on Computer Applications in Shipbuilding 2009 (ICCAS09), pages 181- 186, Shanghai, 2009.

[99] Mohan, C. K. Discrete Particle Swarm Optimization, Workshop on Particle Swarm Optimization / C. K. Mohan and B. Al-Kazemi // Indianapolis, Purdue School of Engineering and Technology, 2001.

[100] Morley, R. Painting trucks at General Motors: the effectiveness of a complexity-based approach / R. Morley // Embracing Complexity: exploring and application of complex adaptive systems to business 1996. P. 53-58.

[101] Nemhauster, G. L. Branch-and-bound and Parallel Computation: a Historical Note / G. L. Nemhauster, E. A. Pruul, R. A. Rushmeier // Oper. Res. Let., 7, 65-69, 1988.

[102] Papaioannou, S.G. Optimal test generation in combinational networks by pseudo-Boolean programming / S. G. Papaioannou // IEEE Transactions on Computers 26 (1977), 553-560.

[103] Prampero, P.S. Magnetic Particle Swarm Optimization / P.S. Prampero, R. Attux // Proceedings of the IEEE Swarm Intelligence Symposium (SIS2011), Paris, France, 2011.

[104] Pelikan, M. BOA: Bayesian optimization algorithm / M. Pelikan, D. E. Goldberg, E. Cantu-Paz // Proceeding of Genetic and Evolutionary Computation Conference GECCO-99, Vol. I, p. 525-532. Orlando, FL: Morgan Kaufman Publishers, San Francisco, CA, 1999.

[105] Pelikan, M. Bayesian optimization algorithm: From single level to hierarchy/ M. Pelikan // Doctoral dissertaion, University of Illinois at Urbana-Champaign, Urbana, IL, 2002.

[106] Pelikan, M. A Survey of Optimization by Building and Using Probabilistic Model / M. Pelikan, D. E. Goldberg, F. G. Lobo // Computational Optimization and Applications, Kluwer Academic Publishers, Vol. 21, pp. 5-20, 2002.

[107] Pena, J. GA-EDA: Hybrid Evolutionary Algorithm Using Genetic and Estimation of Distribution Algorithms / J. Pena, V. Robles, P. Larranaga, V. Herves, F. Rosales, and M. Perez // Innovations In Applied Artificial

Intelligence: 17th International Conference on Industrial and Engineering Applications of Artificial Intelligence and Expert Systems, IEA/AIE 2004, Ottawa, Canada, May 17-20, 2004: Proceedings, 2004.

[108] Peng, B. Differential evolution algorithm-based parameter estimation for chaotic systems / B. Peng, B. Liu, F. -Y. Zhang, L. Wang // Chaos, Solitons and Fractals 39, 2110-2118, 2009.

[109] Pedersen, J. Genetic algorithms for protein structure prediction / J. Pedersen, J. Moult // Curr. Opin. Struct. Biol., vol. 6, no. 2, pp. 227-231, 1996.

[110] Picard, J.C. A cut approach to the rectilinear facility location problem / J.C. Picard, H.D. Ratliff// Operations Research 26 (1978), 422-433.

[111] Quaranta, G. Parameters identification of Van der Pol-Duffing oscillators via particle swarm optimization and differential evolution / G. Quaranta, G. Monti and G. C. Marano // Mechanical Engineering and Signal Processing, 2009.

[112] Ranyard, R.H. An algorithm for maximum likelihood ranking and Slater's i from paired comparisions / R.H. Ranyard // British Journal of Mathematical and Statistical Psychology 29 (1976), 242-248.

[113] Rao, M.R. Cluster analysis and mathematical programming / M.R. Rao // Journal of the American Statistical Association 66 (1971), 622-626.

[114] Rinnoy Kan, A.H.G. Stochastic Global Optimization Methods / A.H.G. Rinnoy Kan, G.T. Timmer // Mathematical programming, 39, 27-78, 1987.

[115] Robinson, G.E. Regulation of vision of labor in insect societies / G.E. Robinson // Annu. Rev. Ectomol. 1992.37 P. 637-665.

[116] Salustowicz, R.P. Probabilistic Incremental Program Evolution / R.P. Salustowicz, J. Schmidhuber // Evol. Corrrput., Vol. 5, No. 2, pp. 123-141, 1997.

[117] Schaffer, J.D. Real-Coded Genetic Algorithms and Interval-schemata / J.D. Schaffer // Foundations of Genetic Algorithms 2. By L.J. Eshelman. San Mateo: Morgan Kaufmann. pp 187-202, 1993.

[118] Schwefel, H.-R Evolution and Optimum Seeking / H.-R Schwefel. — Wiley & Sons, 1995.

[119] Shan, Y. A Survey of Probabilistic Model Building Genetic Programming / Y. Shan, R.I. McKay, D. Essam and H. A. Abbass // M. Pelikan, K. Sastry and E. Cant 'u-Paz, editors, Scalable Optimization via Probabilistic Modeling: From Algorithms to Applications, pp. 121-160, 2006.

[120] Shi, Y. A modified particle swarm optimizer / Y. Shi; R.C. Eberhart // Proceedings of IEEE International Conference on Evolutionary Computation, pp. 69-73, 1998.

[121] Simeone, B. Quadratic 0-1 programming, Boolean functions and graphs / B. Simeone // Ph.D. thesis in COMBINATORICS AND OPTIMIZATION, Waterloo, 1979/

[122] Streichert, F. Comparing Discrete and Continuous Genotypes on the Constrained Portfolio Selection Problem / F. Streichert, H. Ulmer, A. Zell // Proceedings of the genetic and evolutionary computation conference, part ii (pp. 1239-1250). Seattle, Washington, USA: Springer-Verlag, Lecture Notes in Computer Science Vol. 3103.

[123] Stron, R. Differential Evolution — A Simple and Efficient Heuristic for Global Optimization over Continuous Spaces / R. Storn, K. Price // Journal of Global Optimization, vol. 11, pp. 341-359, 1997.

[124] Tang M. A hybrid genetic algorithm for the optimal constrained web service selection problem in web service composition / M. Tang, L. Ai // Proceeding of the 2010 World Congress on Computational Intelligence, 2010. URL: http://eprints.qut.edu.au/33293/l/c33293.pdf.

[125] Torn, A. Global Optimization as a Combination of Global and Local Search / A. Torn // Turku, Abo Akademi University, HHAA A: 13, 1974.

[126] Torn, A. Topographical Global Optimization / A. Torn, S. Viitanen. // Floudas C.A., Pardalos P.M. (eds): Recent Advances in Global Optimization. Princeton University Press, 384-398, 1992.

[127] Unger, R. On the applicability of genetic algorithms to protein folding / R. Unger, J. Moult // The Twenty-Sixth Hawaii International Conference on System Sciences, 1993, pp. 715-725.

[128] Wang, L. A hybrid quantum-inspired genetic algorithm for flow shop scheduling / L. Wang, H. Wu, F. Tang and D. W. Zheng // Lecture Notes in Computer Science 3465, 636-644. — Berlin: Springer-Verlag, 2005.

[129] Whitley, D. The Genitor algorithm and selection pressure: Why rank-based allocation of reproductive trials is best / D. Whitley. — Proceedings of the Third International Conference on Genetic Algorithms, 1989. — p. 116-121.

[130] Waldspurger, C. A. Spawn: A distributed computational economy / C. A. Waldspurger, T. Hogg, B. A. Huberman, J. O. Kephart. // IEEE Trans. Softw. Engineer. 1992.18 P.103-117.

[131] Wang, Y. Estimation of distribution and differential evolution cooperation for real-world numerical optimization problems / Y. Wang, B. Li, K. Zhang // IEEE Congress on Evolutionary Computation (CEC), 2011. — pp. 1315-1321.

[132] Warszawski, A. Pseudo-Boolean solutions to multidimensional location problems. Operations Research 22, 1081-1085, 1974.

[133] Weingartner, H.M. Capital budgeting of interrelated projects: survey and synthesis. Management Science 12 (1966), 485-516.

[134] Wellman, M. P. A market oriented programming environment and its application to distributed multicommodity flow problems / M. P. Wellman /7 J. Artif. Intel. Res. 1993.1 P. 1-23.

[135] Xiao, J. A quantum-inspired genetic algorithm for data clustering / J. Xiao, Y. P. Yan, Y. Lin, L. Yuan and J. Zhang // Proc IEEE Congress on Evolutionary Computation, Hong Kong, China, 2004.

[136] Yapicioglu, H., Solving the semi-desirable facility location problem using bi-objective particle swarm / H. Yapicioglu, A.E. Smith, G.V. Dozier // European Journal of Operational Research, vol. 177, pp. 733 -749, 2007.

[137] Yang, S. Experimental study on population-based incremental learning algorithms for dynamic optimization problems / S. Yang, X. Yao // Soft Comp., vol. 9, no. 0, pp. 815-834, 2005.

[138] Yang, S. Population-based incremental learning with associative memory for dynamic environments / S. Yang, X. Yao // Evolutionary Computation, IEEE Transactions on, vol. 12, no. 5, pp. 542 -561, 2008.

[139] Yilmaz, A.S. Evolving sensor suites for enemy radar detection / A.S. Yilmaz, B.N. Mcquay, H. Yu, A.S. Wu, and J.C. Sciortino // Genetic and Evolutionary Computation GECCO, 2003.

[140] Zhou, L. An Estimation of Distribution Algorithm based on Nonparametric Density Estimation / L. Zhou, A. Zhou, G. Zhang, C. Shi /7 IEEE Congress on Evolutionary Computation (CEC), 2011. — pp. 1597-1604.

Список публикаций автора

1. Галушин, П.В. Разработка и исследование асимптотического вероятностного генетического алгоритма / П.В. Галушин, О.Э. Семёнкина // Journal of Siberian Federal University. Mathematics & Physics. № 5(1). - 2011. - p. 46-56.

2. Галушин, П.В. Асимптотический вероятностный генетический алгоритм дискретной оптимизации // П.В. Галушин, О.Э. Семёнкина // Вестник Сибирского государственного аэрокосмического университета им:, академика М.Ф. Решетнева. № 5 (38). - 2011. - С. 25-29.

3. Галушин, П.В. Автоматизированная система глобальной оптимизации миогоагентными стохастическими алгоритмами / П.В. Галушин, С.Н. Ефимов, Е.С. Семёнкин, И.А. Панфилов // Программные продукты и системы. № 3 (95). — 2011. — С. 97-101.

4. Галушин, П.В. Асимптотический вероятностный генетический алгоритм / П.В. Галушин, Е.С. Семёнкин /7 Вестник Сибирского государственного аэрокосмического университета им. академика М.Ф. Решетнева. ДО 4 (25). — 2009. — С. 37-42.

5. Galushin, P.V. The asymptotic probabilistic genetic algorithm / P.V. Galushin, E.S. Semenkin // Вестник Сибирского государственного аэрокосмического университета им. академика М.Ф. Решетнева. № 5 (26). - 2009. - С. 45-49.

6. Galushin, P., Comparative Analysis of Two Distribution Building Optimization Algorithms / P. Galushin, O. Semenkina, A. Shabalov // In: Distributed Computing and Artificial Intelligence. Advances in Intelligent and Soft Computing, Volume 151. - 2012. - pp. 759-766.

7. Shabalov, A. Integration of Intelligent Information Technologies Ensembles for Modeling and Classification / A. Shabalov, E. Semenkin, P. Galushin // In: Corchado E. et al. (Eds): Hybrid Artificial Intelligent Systems. - Part I. - Lecture Notes in Computer Science. - Volume 7208. - 2012. - Pp. 365-374.

8. Galushin, P.V. Design and analysis of asymptotic genetic algorithm / P.V. Galushin, O.E. Semenkina // Proc. of the 11th International Conference of Natural Computations. — 2011. — p. 1082-1087.

9. Shabalov, A. Automatized design application of intelligent information technologies for data mining problems / A. Shabalov, E. Semenkin, P. Galushin /7 Proc. of the 11th International Conference of Natural Computations. - 2011. - p. 2596-2599.

10. Галушин, П.В. Об асимптотическом вероятностном генетическом алгоритме / П.В. Галушин // Решетнёвские чтения: Материалы XIII Междунар. науч. конф., посвящ. 45-летию Сиб. гос. аэрокосмич. ун-та имени акад. М. Ф. Решетнева. (10-12 ноября 2009, г. Красноярск) / Под общ. ред. С. И. Сенашова. - Сиб. гос. аэрокосмич. ун-т. - Красноярск, 2009. - Ч. 2. - С. 409-411.

И. Галушин, П.В. Динамическое составление расписания адаптивными методами / П. В. Галушин // Вестник университетского комплекса: Сб. науч. трудов / Под общ. ред. профессора Н.В. Василенко. - Красноярск: ВСФ РГУИТП, НИИ СУВПТ. - 2006. - Выпуск 7 (21). - С. 111-115.

12. Галушин, П.В. Автоматизированная система решения сложных задач глобальной оптимизации многоагентными стохастическими алгоритмами (GOLEM-SA): свидетельство о государственной регистрации программы для ЭВМ / П.В. Галушин, С.С. Бежитский, и др. — М.: Реестр программ для ЭВМ, 2011. Номер гос. per. №2011611158.

13. Галушин, П.В. Асимптотический вероятностный генетический алгоритм (APGA): свидетельство о государственной регистрации

программы для ЭВМ / П.В. Галушин — М.: Реестр программ для ЭВМ, 2012. Номер гос. per. №2012612374.