Генетический алгоритм (ГА). Задача алгоритма состоит в максимизации функции приспособленности.
Формально, схема ГА может быть представлена следующим образом (популяция t-го поколения обозначается как {Sk(t)}):
Шаг 0. Создать случайную начальную популяцию {Sk(0)}.
Шаг 1. Вычислить приспособленность f(Sk) каждой особи Sk популяции {Sk(t)}.
Шаг 2. Производя отбор особей Sk в соответствии с их приспособленностями f(Sk) и применяя генетические операторы (рекомбинации и точечные мутации) к отобранным особям, сформировать популяцию следующего поколения {Sk(t+1)}.
Шаг 3. Повторить шаги 1,2 для t = 0, 1, 2,..., до тех пор, пока не выполнится некоторое условие окончания эволюционного поиска (прекращается рост максимальной приспособленности в популяции, число поколений t достигает заданного предела и т.п.).
Достоинства эволюционных вычислений:
1. широкая область применения;
2. возможность проблемно-ориентированного кодирования решений, подбора начальной популяции, комбинирования эволюционных вычислений с неэволюционными алгоритмами, продолжения процесса эволюции до тех пор, пока имеются необходимые ресурсы;
|
|
3. пригодность для поиска в сложном пространстве решений большой размерности;
4. отсутствие ограничений на вид целевой функции;
5. ясность схемы и базовых принципов эволюционных вычислений;
6. интегрируемость эволюционных вычислений с другими неклассическими парадигмами искусственного интеллекта, такими как искусственные нейросети и нечеткая логика.
Недостатки эволюционных вычислений:
1. эвристический характер эволюционных вычислений не гарантирует оптимальности полученного решения;
2. относительно высокая вычислительная трудоемкость, которая однако преодолевается за счет распараллеливания на уровне организации эволюционных вычислений и на уровне их непосредственной реализации в вычислительной системе;
3. относительно невысокая эффективность на заключительных фазах моделирования эволюции.