Скажем несколько слов об основе ГА – эволюционном подходе к решению задачи. Такой подход предполагает, что в процессе решения, решающий будет опираться на некоторые принципы естественного (или эволюционного) развития. Как правило, это принцип наследственности и принцип естественного отбора. В настоящее время применение такого подхода отнюдь не ограничивается задачами оптимизации, но мы остановимся только на ГА как на четкой конкретизации этого подхода для решения оптимизационных задач.
В общих чертах, ГА представляет собой модель естественного развития некоторой популяции особей (индивидов), где заданы все основные природные процессы: фактор приспособленности особи к окружающей среде, воспроизводство и естественный отбор особей в соответствии с их приспособленностью. При работе алгоритма мы должны пронаблюдать эволюцию нашей популяции по фактору приспособленности, и в результате получить самого приспособленного индивида.
Для конкретной задачи оптимизации, каждый индивид является решением задачи записанным в форме какого-либо единого представления параметров, например строки. Отметим, что под решением мы понимаем некие значения параметров, соответствующие условиям задачи и дающие какой-либо, не обязательно желаемый, результат целевой функции. Это представление параметров играет роль цепочки генов для данного индивида. Именно с ней и происходят все действия. Отсюда и название – генетический алгоритм. Фактор приспособленности индивида есть мера «пригодности» данного решения (т.е. насколько оно удовлетворяет запросам составителя алгоритма), и роль его является ведущей. Как правило, это значение целевой функции. Процесс воспроизводства, есть некоторый оператор получения новых решений из уже имеющихся, для организации перебора. Следует сказать, что в общем понимании, ГА – это именно схема для построения алгоритма, а не конкретный алгоритм.
Loading ...