Аналитическая часть. 
Генетические алгоритмы и традиционные способы оптимизации

Генетические алгоритмы и традиционные способы оптимизации

Описание генетических алгоритмов

Согласованность и эффективность работы элементов биологических организмов наводит на мысль о возможности использования принципов биологической эволюции с целью оптимизации практически важных для человека систем.

В 1975 г. вышла основополагающая книга Дж. Холланда (Holland) ЇАдаптация в естественных и искусственных системах, в которой был предложен генетический алгоритм — алгоритм, основанный на принципах естественного отбора Ч.Дарвина.

Генетические алгоритмы относят к области мягких вычислений. Понятие «мягких вычислений» (Лофти Заде, 1994 г.) подразумевает под собой совокупность неточных, приближенных методов решения задач, зачастую не имеющих решение за полиномиальное время. Такие задачи возникают в области биологии, медицины, гуманитарных наук, менеджменте. Методы мягких вычислений хорошо дополняют друг друга, и часто используются совместно. В область мягких вычислений входят такие методы как:

• — нечеткая логика;
• — нейронные сети;
• — вероятностные рассуждения;
• — байесовские сети доверия;
• — эволюционные алгоритмы. [5]

Генетический алгоритм представляет собой метод, отражающей естественную эволюцию методов решения проблем, и в первую очередь задач оптимизации.

Генетические алгоритмы — это процедуры поиска, основанные на механизмах естественного отбора и наследования. В них используется эволюционный принцип выживания наиболее приспособленных особей. Они отличаются от традиционных методов оптимизации несколькими базовыми элементами. В частности, генетические алгоритмы обладают рядом отличительных свойств:

• 1. кодирование параметров — генетические алгоритмы обрабатывают не значения параметров самой задачи, а их закодированную форму
• 2. операции на популяции — генетические алгоритмы осуществляют поиск решения исходя из единственной точки (начальное приближение) а из некоторой популяций
• 3. использование минимума информаций о функций — генетические алгоритмы используют только целевую информацию, а не производные либо дополнительную информацию
• 4. рандомизация информаций — генетические алгоритмы применяют вероятностные, а не детерминированные правила выбора

Байесовские сети доверия — модель вероятностных и причинно-следственных отношений между переменными в статистическом информационном моделировании.

Сфера применения генетических алгоритмов — это в основном оптимизация многопараметрических функций. Прикладное же применение генетических алгоритмов весьма обширно. Они применяются при разработке программного обеспечения в системах искусственного интеллекта, оптимизации, искусственных нейронных сетях и в других отраслях знаний. Следует отметить, что с их помощью решаются задачи, для которых ранее использовались нейронные сети. В этом случае генетические алгоритмы выступают просто в роли независимого от нейронных сетей метода, предназначенного для решения той же самой задачи. Примером может служить задача коммивояжера, изначально решавшаяся при помощи сети Хопфилда¹. Генетические алгоритмы часто используются совместно с нейронными сетями. Они могут поддерживать нейронные сети или наоборот, либо оба метода взаимодействуют в рамках одной гибридной системы, предназначенной для решения конкретной задачи. Генетические алгоритмы так же применяются совместно с нечеткими системами.

Целесообразность использования генетических алгоритмов изложена очень емко и кратко во фразе из статьи К. Де Йонга: «Решающий аргумент при использовании генетических алгоритмов тесно связан с вопросом о том, какое пространство поиска будет исследовано. Если это пространство легко анализировать и его структура позволяет использовать специализированные методы поиска, то использование генетических алгоритмов менее эффективно с точки зрения затрат вычислительных ресурсов. Если же пространство поиска не поддается анализу и относительно слабо структурировано, и если возможен эффективный способ представления в генетических алгоритмах этого пространства, то они оказываются удивительно эффективным методом эвристического поиска в больших и сложных областях». [8].

Но не стоит расценивать генетические алгоритмы как своеобразную панацею для задач оптимизации. С большой вероятностью генетические алгоритмы покажут как минимум не лучшие результаты по сравнению со специально разработанными методами для решения специализированных задач. Большой плюс эволюционных вычислений в предоставляемом ими унифицированном подходе к решению самых различных проблем.

Генетические алгоритмы показывают блестящие результаты при решении сложных переборных задач (большинство из которых NP-полные, т. е. не решаются полным перебором за полиномиальное время), таких, например, как задача коммивояжера и поиск булевых термов.

генетический алгоритм популяция.