Разработка и исследование вероятностных эволюционных алгоритмов для моделирования и оптимизации сложных систем
Диссертация - Менеджмент
Другие диссертации по предмету Менеджмент
ачи в тестовом наборе должны быть непохожи друг на друга, чтобы у создателя алгоритма было меньше возможностей настроить его на специальных примерах.
-В тестовых задачах должны содержаться такие ситуации, которые обычно вызывают затруднения; процесс проверки алгоритма должен показать, что эти трудности преодолеваются. [4]
-Тестовые задачи должны вызывать затруднения у локальных методов.
-Тестовые задачи должны быть нелинейными и несепарабельными.
-Тестовые задачи должны быть масштабируемыми. [60]
Наиболее часто для проверки эффективности адаптивных алгоритмов глобального поиска используются функции Розенброка, Шекеля, Растригина, Катникова, Griewank, De Jong. Общая схема проектирования многоэкстремальных тестовых функций предложена в [14, 16]. Подробно схема проектирования тестовых функций непрерывных переменных представлена в Приложении 1. Набор тестовых функций, используемых в диссертации, представлен в Приложении 2. Используемые тестовые функции реализуют многие свойства, затрудняющие оптимизацию: многоэкстремальность, несепарабельность, овражность, множества постоянства, значения функции в глобальном оптимуме слабо отличается от значений в локальных и др.
1.2Стандартный генетический алгоритм и исследование его работоспособности на тестовых задачах
Эволюционные алгоритмы (ЭА), предложенные впервые для решения задач адаптации, в дальнейшем интенсивно развивались как методы решения сложных задач оптимизации. Генетические алгоритмы (ГА) представляют собой семейство ЭА, имеющих общую схему. На сегодняшний день ГА доказали свою конкурентоспособность при решении многих NP-трудных задач поиска и оптимизации и особенно в практических приложениях, где математические модели имеют сложную структуру и применение классических методов невозможно.
В основе большинства концепций искусственного интеллекта лежит богатое разнообразие природных явлений. Один из примеров - искусственные нейронные сети, основная идея которых основывается на функционировании нейронов мозга. ГА являются направлением более общей теории ЭА, основанной на следующем принципе: каждый биологический вид целенаправленно развивается и изменяется для того, чтобы наилучшим образом приспособиться к окружающей среде.
ЭА базируются на коллективном обучающем процессе внутри популяции индивидуумов, каждый из которых представляет собой поисковую точку в пространстве допустимых решений данной задачи. Популяция случайно инициализируется, и затем охватывает лучшие регионы поискового пространства посредством случайных процессов селекции, мутации и рекомбинации. Окружающая среда представляет качественную информацию (степень пригодности) о поисковых точках (индивидуумах), а процесс селекции отбирает тех индивидуумов, у которых значение пригодности выше. Отобранные потомки являются, в свою очередь, родителями в следующем поколении. Механизм рекомбинации перемешивает генетическую информацию родителей (тем самым рождается один или несколько потомков), и наконец, механизм мутации способствует в некоторой степени обновлению генетической информации потомков. [18]
В 1975 г. вышла основополагающая книга Дж. Холланда Адаптация в естественных и искусственных системах, в которой был предложен первый генетический алгоритм. Термин "генетические алгоритмы" ввел в 1975 г. Д. Голдберг [43]. Его книга содержит детальное обсуждение, как теоретических аспектов ГА, так и возможных областей их применения:
-Искусственная жизнь,
-Автоматическое обучение,
-Извлечение данных (знаний),
-Инженерное проектирование,
-Планирование и управление,
-Моделирование, идентификация,
-Численная и комбинаторная оптимизация.
Итак, ГА базируются на теоретических достижениях синтетической теории эволюции, учитывающей микробиологические механизмы наследования признаков в природных и искусственных популяциях организмов, а также на накопленном человечеством опыте в селекции животных и растений.
Методологическая основа ГА зиждется на гипотезе селекции, которая в самом общем виде может быть сформулирована так: чем выше приспособленность особи, тем выше вероятность того, что в потомстве, полученном с ее участием, признаки, определяющие приспособленность, будут выражены еще сильнее [3].
Т.о. ГА заимствуют из биологии:
-понятийный аппарат;
-идею коллективного поиска экстремума при помощи популяции особей;
-способы представления генетической информации;
-способы передачи генетической информации в череде поколений (генетические операторы);
-идею о преимущественном размножении наиболее приспособленных особей.
1.2.1Представление решений в ГА
Подобно тому, как природный хромосомный материал представляет собой линейную последовательность различных комбинаций четырех нуклеотидов, решения в ГА представляются в виде хромосом (генотипов). Генотип - строка конечной длины, состоящая из генов, представленных символами некоторого алфавита.
В ГА существует строгое различие между фенотипом (решением, выраженным в терминах поставленной задачи) и генотипом (хромосомой, представлением решения). ГА работает с генотипом, фенотип служит для определения пригодности индивида (оценки качества решения поставленной задачи), поэтому для работы алгоритма необходимо определить некоторую функцию кодирования (, где - пространство поиска, - пространство представлений решений) и функцию декодирования