Генетические алгоритмы оптимизации
Опубликовано: 12.10.2017
Появившись на свет в качестве упрощенного описания эволюционных перестроек в природных популяциях организмов, генетические алгоритмы (ГА) стараниями многочисленных исследователей на сегодняшний день превратились в мощную поисковую процедуру, ориентированной на решение задач глобальной оптимизации в самом широком диапазоне возможных применений – от создания алгоритмов поиска в распределенных базах данных в условиях высокой степени неопределенности исходных критериев (Data Mining) до решения прикладных задач при проектировании современных технических устройств (в том числе и средств измерений).
ГА базируются на теоретических достижениях теории эволюции, учитывающей микробиологические механизмы наследования признаков в природных и искусственных популяциях организмов, а также на накопленном человечеством опыте в селекции животных и растений.
В основе ГА основана на гипотезе селекции, которая в самом общем виде может быть сформулирована так: чем выше приспособленность особи, тем выше вероятность того, что в потомстве, полученном с ее участием, признаки, определяющие приспособленность, будут выражены еще сильнее.
Генетический алгоритм. Размещение графа на линейке
Применительно к техническим системам под особью будет подразумеваться тот или иной вариант ее реализации (или вариант принимаемого решения), а под приспособленностью – способность наиболее полно удовлетворять набору исходных требований- критериев (другими словами - оптимальность). Таким образом, ГА представляют собой семейство методов оптимизации.
Представим себе, что нам необходимо спроектировать самолет, который должен с максимальной скоростью (критерий 1) перевозить максимальное количество груза (критерий 2) на максимальное расстояние (критерий 3). После формирования набора критериев и допустимых диапазонов их изменения мы формируем набор параметров, наиболее полным образом характеризующих наш технический объект (размер и форма фюзеляжа и крыльев, количество и тип двигателей, материал обшивки, объем топливных баков и т. д.). Затем мы строим математическую модель и начинаем эксперименты с ней.