Содержание
- Введение
- 1. Актуальность темы.
- 2. Цель и задачи исследования .
- 3. Обзор исследований и разработок .
- 4. Представление вещественных решений в двоичной форме .
- Заключение
Введение
В настоящее время быстро развивается новое направление в теории и практике искусственного интеллекта – эволюционные вычисления (ЭВ). Особенности идей эволюции и самоорганизации заключаются в том, что они находят подтверждение не только для биологических систем, развивающихся много миллиардов лет. Эти идеи в настоящее время с успехом используются при разработке многих технических и, в особенности, программных систем. Генетические алгоритмы (ГА) были разработаны американским исследователем Холландом. Голдберг (ученик Холланда) успешно развил ГА и расширил области его применения. Также в 60-х годах в Германии И. Рехенберг заложил основы "эволюционных стратегий" (ЭС). В науке и технике эволюционные вычисления используются в качестве адаптивных алгоритмов для решения практических задач и как вычислительная модель эволюции естественных систем. ЭВ успешно применяются при решении сложных задач в технических разработках и в бизнесе. С помощью ЭВ было разработано много промышленных проектных решений, которые позволили сэкономить миллионы долларов. ЭВ широко используются для прогнозирования развития финансовых рынков, инвестиций и т.п. Методы ЭВ обычно используются для оценки и выбора (суб)оптимальных непрерывных параметров моделей большой размерности, для решения различных NP-полных комбинаторных задач, в системах извлечения знаний из больших баз данных (Data mining) и многих других областях науки и техники. После того, как компьютерные системы стали достаточно быстродействующими и недорогими, ЭВ превратились в важнейший инструмент поиска субоптимальных решений задач, которые до этого считались неразрешимыми
1.Актуальность темы
Магистерская работа посвящена актуальной научной задаче разработки WEB-интерфейса для реализации генетического алгоритма. ГА используют принципы и терминологию, заимствованные у биологической науки – генетики. В ГА каждая особь представляет потенциальное решение некоторой проблемы. В классическом ГА особь кодируется строкой двоичных символов – хромосомой, каждый бит которой называется геном. Множество особей – потенциальных решений составляет популяцию. Поиск (суб)оптимального решения проблемы выполняется в процессе эволюции популяции - последовательного преобразования одного конечного множества решений в другое с помощью генетических операторов репродукции, кроссинговера и мутации. ЭВ используют следующие механизмы естественной эволюции: 1) Первый принцип основан на концепции выживания сильнейших и естественного отбора по Дарвину, который был сформулирован им в 1859 году в книге «Происхождение видов путем естественного отбора». Согласно Дарвину особи, которые лучше способны решать задачи в своей среде, выживают и больше размножаются (репродуцируют). В генетических алгоритмах каждая особь представляет собой решение некоторой проблемы. По аналогии с этим принципом особи с лучшими значениями целевой (фитнесс) функции имеют большие шансы выжить и репродуцировать. Формализация этого принципа, как мы увидим далее, дает оператор репродукции. 2) Второй принцип обусловлен тем фактом, что хромосома потомка состоит из частей полученных из хромосом родителей. Этот принцип был открыт в 1865 году Менделем. Его формализация дает основу для оператора скрещивания (кроссинговера). 3) Третий принцип основан на концепции мутации, открытой в 1900 году де Вре. Первоначально этот термин использовался для описания существенных (резких) изменений свойств потомков и приобретение ими свойств, отсутствующих у родителей. По аналогии с этим принципом генетические алгоритмы используют подобный механизм для резкого изменения свойств потомков и тем самым, повышают разнообразие (изменчивость) особей в популяции (множестве решений).
2. Цель и задачи исследования
В моей магистерской работе описан процесс реализации классического генетического алгоритма с помощью языка программирования PHP. Основной целью исследования является разработка WEB-интерфейса для работы с генетическим алгоритмом. Основные задачи исследования: 1. Привести основные этапы разработки WEB-интерфейса 2. Описать работу генетического алгоритма, привести его структурную схему. 3. Составить программа на языке PHP 4. Разработать приложение, показывающее работу алгоритма.
3. Обзор исследований и разработок
Генетические алгоритмы (ГА) были разработаны американским исследователем Холландом. Голдберг (ученик Холланда) успешно развил ГА и расширил области его применения. Также в 60-х годах в Германии И. Рехенберг заложил основы "эволюционных стратегий" (ЭС). В основу данной работе были положены 3 принципа механизмов естественной эволюции: 1) принцип естественного отбора по Дарвину, который был сформулирован им в 1859 году в книге «Происхождение видов путем естественного отбора». 2) Принцип который обусловлен тем фактом, что хромосома потомка состоит из частей полученных из хромосом родителей. Этот принцип был открыт в 1865 году Менделем. Его формализация дает основу для оператора скрещивания (кроссинговера). 3) Третий принцип основан на концепции мутации, открытой в 1900 году де Вре.
4. Представление вещественных решений в двоичной форме
В предыдущем примере мы рассматривали только целочисленные решения. Обобщим ГА на случай вещественных чисел на следующем примере, в котором для функции f(x)=(1,85 -x)*cos(3,5x – 0,5), представленной на рис.1.5 необходимо найти вещественное , которое максимизирует f, т.е. такое , для которого для всех х .
Пример функции с популяцией особей в начале эволюции
Нам необходимо построить ГА для решения этой задачи. Для представления вещественного решения (хромосомы) будем использовать двоичный вектор, который применяется в классическом простом ГА. Его длина зависит от требуемой точности решения, которую в данном случае положим 3 знака после запятой. Поскольку отрезок области решения имеет длину 20, для достижения заданной точности отрезок [-10,+10] должен быть разбит на равные части, число которых должно быть не менее 20*1000. В качестве двоичного представления используем двоичный код номера отрезка. Этот код позволяет определить соответствующее ему вещественное число, если известны границы области решения. Отсюда следует, что двоичный вектор для кодирования вещественного решения должен иметь 15 бит, поскольку 16384= <20000 Это позволяет разбить отрезок [-10,+10] на 32768 частей и обеспечить необходимую точность. Отображение из двоичного представления ( ) ( ) в вещественное число из отрезка [-10,+10] выполняется в два шага. 1) Перевод двоичного числа в десятичное: 2) Вычисление соответствующего вещественного числа х: , где – 10 левая граница области решения. Естественно хромосомы (000000000000000) и (111111111111111) представляют границы отрезка –10 и +10 соответственно. Очевидно, при данном двоичном представлении вещественных чисел можно использовать классический простой ГА. На рис.1.5–рис.1.8 представлено расположение особей - потенциальных решений на различных этапах ГА в процессе поиска решения. На рисунке 1.5 показана начальная популяция потенциальных решений, которая равномерно покрывает область поиска решения. Далее явно видно, как постепенно с увеличением номера поколения особи "конденсируются" в окрестностях экстремумов и в конечном счете находится лучшее решение.
Рисунок 2 – Начальная «конденсация» особей популяции в окрестностях экстремумов
Конденсация» особей в окрестностях эксремумов
Рисунок 4 – Положение особей популяции в конце эволюции
Рисунок 5 – Положение особей популяции в конце эволюции
Заключение
Задачей данного курсового проекта была реализация WEB-интерфейса, реализующего генетический алгоритм. Данный WEB-интерфейс был успешно создан, протестирована его функциональность и эффективность.