| Генетический алгоритм — это алгоритм поиска решения определённой задачи, основанный на эвристике. Круг решаемых задач несколько узок: в основном, это задачи оптимизации и моделирования. Поиск решения осуществляется путём случайного подбора, комбинирования и вариации искомых параметров с использованием методов, напоминающих биологическую эволюцию. Генетический алгоритм является разновидностью эволюционных вычислений. Задача кодируется таким образом, чтобы её решение можно было представить в виде набора коэффициентов — генов. Это, пожалуй, единственное ограничение, и если это возможно, то задача вполне успешно будет решаться генетическим алгоритмом. То есть основная сложность — представление (интерпретация) решения задачи в необходимом виде. Первоначально создаётся первая популяция (набор решений), гены которой определены случайным образом, в след за этим для каждого варианта решения определяется значение fitness-функции. Fitness-функция — это целевая функция, то есть мера точности решения или мера удовлетворения решению задачи. Увеличением значения fitness-функции и занимается генетический алгоритм. Определив fitness-функции и подсчитав их для каждого варианта, отбираются лучшие гены, которые будут переданы следующему поколению вариантов решений. Таким образом, через несколько поколений будет найдено (если это возможно) хорошее решение поставленной задачи. В качестве примера привожу график из моей статьи (ИжГТУ 2008) :
GA_graph | Генетический алгоритм На графике представлены максимальные и средние из всей популяции значения фитнесс-функции для каждой эпохи. Коэффициенты подбирались для нейронной сети, задача была не простая — обучение механизмов правильному движению. И тем не менее, за небольшое количество эпох уже был найден хороший вариант. В качестве дополнения привожу одну из моих реализаций генетического алгоритма, простой и одновременно отличный вариант: void GeneticPool::Evolve(int diversity, float mutationPower)
{
SortByFitness(); // сортировка генов for (int i = diversity; i < genesCount; i++)
{
Genes[i] = MutateGenes(Genes[RandomInt(diversity)], MutationPower);
}
} Значение diversity определяет количество особей, гены которых будут переданы следующему поколению. Сами эти особи изменению не подвергнутся, дабы не потерять лучшие решения. Таким образом мы получили отличный вариант генетического алгоритма.
Источник: http://www.gamedev.ru/code/terms/Genetic_Algorithm | 