Изучение и анализ рынка товаров, закупаемых и реализуемых торгово-закупочным предприятием (на примере Белгородского территориального фонда обязательного медицинского страхования)

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

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

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

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

Возможные случаи применения генетического алгоритма

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

Достоинство генетического алгоритма состоит в том, что он способен манипулировать одновременно многими параметрами. Пусть есть реальная задача поиска оптимального решения. Если пространство поиска, которое предстоит исследовать, большое, и предполагается, что оно не совершенно гладкое и не является унимодальным (содержащим один гладкий экстремум) или не очень понятно, или если функция приспособленности с шумами, или если задача не требует строго нахождения глобального оптимума - т.е. если достаточно быстро просто найти приемлемое "хорошее" решение (не всегда наилучшее) - генетический алгоритм будет работать эффективно, превосходя другие методы, которые не используют знания о пространстве поиска.

Но бывают случаи, когда генетический алгоритм не работает эффективно.

Если пространство поиска небольшое, то наилучшее возможное решение может быть найдено методом полного перебора. Переборный метод наиболее прост в программировании. Для поиска оптимального решения (точки минимума целевой функции) требуется последовательно вычислить значения целевой функции во всех возможных точках, запоминая минимальное из них. Недостатком этого метода является большая вычислительная стоимость.

Метод градиентного спуска работает очень быстро, но не гарантирует оптимальности найденного решения. Он хорош для применения в унимодальных задачах, где целевая функция имеет единственный локальный экстремум (он же - глобальный). При этом выбираются некоторые случайные значения параметров, а затем эти значения постепенно изменяют, добиваясь наибольшей скорости "улучшения" значения целевой функции. Достигнув локального экстремума, такой алгоритм останавливается.

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

Символьная модель генетического алгоритма

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

Структура данных генетического алгоритма состоит из одной или большего количества хромосом (обычно из одной). Как правило, хромосома - это битовая строка, так что термин строка часто заменяет понятие "хромосома". В принципе, генетические алгоритмы не ограничены бинарным представлением. Пока ограничимся только структурами, которые являются одиночными строками по l бит.

Каждая хромосома (строка) представляет собой конкатенацию ряда подкомпонентов называемых генами. Гены располагаются в различных позициях или локусах хромосомы, и принимают значения, называемые аллелями. В представлениях с бинарными строками, ген - бит, локус - его позиция в строке, и аллель - его значение (0 или 1). Биологический термин "генотип" относится к полной генетической модели особи и соответствует структуре в генетического алгоритма. Термин "фенотип" относится к внешним наблюдаемым признакам и соответствует вектору в пространстве параметров. Простой пример - задача максимизации функции от нескольких переменных.

 Скачать реферат