Xl Туполевские чтения : всероссийская (с международным участием) молодежная научная конференция. Казань, 8-10 октября 2003 г., тезисы докладов. Т. 3

о решении задачи многокритериальной оптимизации генетическими алгоритмами А.В. Гуменникова Научный руководитель: Е.С. Семёнкин, д.т.н., профессор Сибирский государственный аэрокосмический университет им. М.Ф. Решетнёва При решении многокритериальных оптимизационных задач часто воз­ никает дилемма, какой из критериев взять за приоритетный. Но как пока­ зывает опыт, решение находится в компромиссе - одновременном учете всех целевых функций. В результате получается множество альтернатив­ ных решений, которые принято называть Парето-оптимальными решения­ ми (множеством Парето). Эволюционные алгоритмы обладают рядом характеристик, которые де­ лают их более предпочтительными, чем классические методы многокрите­ риальной оптимизации: они подходят для задач большой размерности и способны захватить Парето-оптимальные точки даже при одном прогоне алгоритма. В качестве основного алгоритма решения многокритериальных задач в теории эволюционных алгоритмов используется процедура общего генетического алгоритма. При этом модифицируются этапы назначения пригодности и селекции, которые реализуются различными методами та­ ким образом, чтобы направить поиск к Парето-оптимальному множеству и обеспечить разнообразие а популяции, для предотвращения преждевре­ менной сходимости и достижения хорошо распределенного (представи­ тельного) недоминируемого множества. Была исследована работа 4 методов (1. VEGA (Schaffer 1985), 2. FFGA (Fonseca and Fleming 1993), 3. NPGA (Horn, Nafpliotis and Goldberg 1994) и 4. SPEA (Zitzler and Thiele 1998)) на 2-х и 3-хкритериальных задачах ми­ нимизации с критериями - квадратичными функциями общего вида: /(1|,ж^) = (дг, -Н2|)" -H(jCj -HZj)' -*min, где 2, и Zj - любые числа. Наилуч­ шие результаты показал метод SPEA. При его реализации за счет того, что во внешнем множестве хранятся недоминируемые точки, в результате обеспечивается хорошая аппроксимация Парето-оптимального фронта, а количество индивидов во внешнем множестве и разнообразие популяции регулируется с помощью образования кластеров. Также достоинством это­ го метода является возможность априорного задания количества точек- решений, получаемых при работе алгоритма. 7