Генетические алгоритмы

Игорь - учится в магистратуре Казанского государственного технического университета имени А.Н. Туполева (ранее КАИ), на факультете технической кибернетики и информатики

Гончаров Дмитрий Александрович - закончил Тульское высшее артиллерийское инженерное училище, начальник отделения программирования.

Яковенко Олег Юрьевич - 1965 г.р. В настоящее время работаю в Казахстане. ОАО "Алюминий Казахстана" Краснооктябрьский бокситовый рудник. Начальник бюро горного проектирования + ведущий инженер - программист. Образование : горный инженер + пользователь САПР. По опыту работу : инженер-проектировщик ( стаж 3 года ), инженер - программист ( стаж с 1992 года ). Языки : С++ Задачи : горно-геометрическое моделирования. Горно-технологическое моделирование. Оптимизация параметров карьеров. Смежные области : Нейронные сети, генетические алгоритмы, имитационное моделирование.

Дмитрий Горбиков - магистрант 2001 года Ульяновского государственного технического университета. Основная работа - Пенсионный фонд России, системщик.

Анюта - учится в МАИ на факультете "Системы автоматического управления ЛА"., тема диплома "Интеллектуальная многоуровневая система выбора маршрута движущегося объекта, основанная на ГА"

Алтынай - аспирантка, специальность математик, занимается задачей прогнозирования временных рядов, Алма-Ата, Казахстан.

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

1) Создание структуры решения искомой задачи в виде массива a[i], i=1,...n, где n - максимальное число компонент структуры
Пример: поиск функции y=f(x) наилучшего приближения экспериментальных точек {x_i, y_i}, j=1,...,m, m - число точек в классе полиномов.
Структура определяется битовым массивом , где каждому элементу массива сопоставлен простейший многочлен типа xⁱ, i=1,...n, где n - максимальная степень полинома.
2) Создание показателя эффективности структуры, заполненной конкретными значе-ниями
Пример: Показателем эффективности для нашего примера будет невязка вида
J_a=I₁+I₂+..+I_m, где I_j=(y_j-fa(x_j))²,
где f_a(x) есть сумма всех элементов вида B_aix^ai при a_i = 1, где a - некоторый битовый массив, однозначно определяющий структуру объекта исследования, параметры a_i определяются методом наименьших квадратов.
3) Задание некоторого массива различных структур S_k, k=1,...,N, размерностью N, большей чем число компонент n в структуре
Данный массив можно сгенерировать случайно задав нули и единицы в каждой структуре.
4) Расчет показателей эффективности J_k для каждой структуры S_k.
По формуле заданной в пункте 2.
5) "Естественный" отбор структур по некоторому правилу выбора наилучших струк-тур среди заданного массива структур
Пример: можно по правилу вида
J₀=M(J_k) - среднее значение J_k, если J_k<J₀, то структура остается, иначе "умирает".
Если разница между предыдущим J₀и новым J₀меньше какого-то малого числа, то конец расчета.
6) Замена выбывших структур на новые, "рожденные" от наиболее приспособленных структур с помощью генетических операторов
а) мутация
Замена в структуре одного из значений случайно выбранной компоненты
Пример: из (1, 1, 0, 1, 0, 0, 1, 0) получится (1, 1, 0, 1, 1, 0, 1, 0).
б) инверсия
Перестановка в структуре некоторой ее части наоборот
Пример: из (1, 1, 0, 1, 0, 0, 1, 0) получится (1, 1, 0, 0, 1, 0, 1, 0).
в) кроссинговер
Создание структуры, основанной на двух структурах - заменой одной части первой структуры на ту же область во второй.
Пример: из (A, B, C, D, E) и (a, b, c, d, e) получится (A, B, c, d, E).
7) Повторение этапа 4.

Задача: min f(x) на [a,b]
Создаем структуру типа (n1, n2, n3, ..., nM), ni - 0 или 1. Вычислим x0 по следующему правилу
Первый бит отвечает за расположение точки в первой или второй половине отрезка [a,b] = [a1, b1]. Второй бит отвечает за расположение точки в первой или второй половине отрезка [a1,b1] и т.д. Итак, по структуре мы можем вычислить аргумент и значение функции и соответственно задав функцию эффективности - решить задачу. Для многомерного случая структура удлиняется на второй и следующие аргументы функции.

The Genetic Algorithms Archive - огромный архив информации про генетические алгоритмы, исходные тексты на C++, Lisp, Fortran, большое количество ссылок на английские ресурсы и ассоциации по ГА

MSU GARAGe home page - исследования по ГА в Мичиганском университете