Потребности в решении задач дискретной оптимизации имеют место в различных приложениях и, в первую очередь, при проектировании технических объектов и при управлении сложными процессами. Наиболее важные задачи в этих приложениях относятся к классу NP-трудных и характеризуются большими размерностями. Для решения таких задач применение известных точных методов оптимизации оказывается, как правило, невозможным. Поэтому находят применение приближенные методы оптимизации, среди которых перспективными зарекомендовали себя эволюционные методы. В настоящее время активно изучаются и развиваются три группы эволюционных методов – генетические методы (Genetic Algorithms - GA), методы поведения «толпы» (Particles Swarm Optimization - PSO) и методы «колонии муравьев» (Ant Colony Optimization - ACO).
Начало применению генетических алгоритмов для решения задач оптимизации положил Д.Холланд в 1975 г. [1]. Фундаментальный вклад в развитие GA внес Д.Гольдберг [2]. В дальнейшем генетические алгоритмы успешно применялись для различных задач синтеза конструкций, составления расписаний, маршрутизации транспортных средств, компоновки оборудования, раскроя материалов и др.
Алгоритм PSO первоначально был описан применительно к задачам математической биологии в 1987 г. [3]. Сведения об алгоритмах и результатах решения с помощью методов PSO ряда задач оптимизации приведены, например, в [4,5].
Впервые идея использования для решения оптимизационных задач аналогии с поведением колонии муравьев высказана в 1992 г. [6]. Применение методов ACO показано на примерах задачи коммивояжера, раскроя и упаковки и др. Обзор методов ACO приведен в [7].
Для применения эволюционных методов к решению конкретной задачи нужно, во-первых, сформулировать множество управляемых параметров X, во-вторых, разработать модель приложения в виде алгоритма вычисления целевой функции F(X), в-третьих, разработать алгоритмическую реализацию эволюционного метода. При этом, учитывая приближенность и статистическую природу этих методов, нужно стремиться к получению высокоэффективных алгоритмов с позиции как точности, так и трудоемкости вычислений.
Общая схема вычислений на основе эволюционных методов представлена на рис. 1.
Вычисления начинаются с формирования множества информационных объектов =(,,…), =1,2,…, которые в соответствии с принятой в GA терминологией называют хромосомами (другие возможные названия – агенты, фреймы, кортежи). Хромосома состоит из генов , значения генов называют аллелями, а позиции генов в хромосоме - локусами. Обычно в задачах оптимизации гены отождествляют с управляемыми параметрами. Множество называют популяцией, а состав популяции в конкретный момент вычислений – поколением.
Рис. 1.   Схема эволюционных вычислений
Эволюция представляет собой многошаговый процесс. На каждом шаге формируются новые хромосомы и хромосом отбирается (селектируется) в новое поколение. Формирование хромосом нового поколения происходит с использованием генного материала текущего поколения и с учетом качества этого материала. Качество -й хромосомы оценивается значением целевой функции (), а качество каждого поколения – наилучшим (минимальным) значением целевой функции, полученным на данный момент вычислений.
Список литературы
1. Holland J. Adaptation in Natural and Artificial Systems. – Univ. of Michigan Press, 1975.
2. Goldberg, D. E. Genetic Algorithms in Search, Optimization, and Machine Learning. - Addison-Welsey, 1989.
3. Deneubourg J.-L., Goss S., Pasteels J.M., Fresneau D. and Lachaud J.-P. Self-organization mechanisms in ant societies (II): learning in foraging and division of labor. In: From Individual to Collective. Behavior in Social Insects. - Basel: Birkhauser, 1987.
4. Eberhart, R. C., and Kennedy, J. A New Optimizer Using Particles Swarm Theory, Proc. Sixth International Symposium on Micro Machine and Human Science. // IEEE Service Center, Piscataway, 1995.
5. Eberhart, R. C., Dobbins, R. W., and Simpson, P. Computational Intelligence PC Tools. - Boston: Academic Press , 1996.
6. Dorigo M. Optimization, Learning and Natural Algorithms. PhD thesis, Dipartimento di Electronica. - Politecnico di Milano, 1992.
7. Dorigo M., Caro G., Gambardella L. Ant Algorithms for Discrete Optimization. //Artificial Life, v.5, 1999, # 3.