 |
Интеллектуальная среда дистанционного обучения и дизайна http: econom.misis.ru, fdisto.misis.ru; e-mail: vaosadchy@yandex.ru |
| На главную | Контакты | Выполнить расчёт (запустить приложение) |
|
|||
|
Оптимизация с использованием генетического алгоритма
Первоначальный вариант программы составил Конышев А.В. (МП-05-1)
Генетические алгоритмы (ГА) - это стохастические, эвристические оптимизационные методы, впервые предложенные Холландом (1975). Они основываются на идее эволюции с помощью естественного отбора, выдвинутой Дарвином (1857).
ГА работают с совокупностью особей - популяцией, каждая из которых представляет возможное решение данной проблемы. Каждая особь оценивается мерой ее приспособленности согласно тому, насколько хорошо соответствующее ей решение задачи. В природе это эквивалентно оценке того, насколько эффективен организм при конкуренции за ресурсы. Наиболее приспособленные особи получают возможность воспроизводить потомство с помощью "перекрестного скрещивания" с другими особями популяции. Это приводит к появлению новых особей, которые сочетают в себе некоторые характеристики, наследуемые ими от родителей. Наименее приспособленные особи с меньшей вероятностью смогут воспроизвести потомков, так что те свойства, которыми они обладали, будут постепенно исчезать из популяции в процессе эволюции. Иногда происходят мутации, или спонтанные изменения в генах.
Таким образом, из поколения в поколение, хорошие характеристики распространяются по всей популяции. Скрещивание наиболее приспособленных особей приводит к тому, что исследуются наиболее перспективные участки пространства поиска. В конечном итоге популяция будет сходиться к оптимальному решению задачи. Преимущество генетических алгоритмов состоит в том, что он находит приблизительные оптимальные решения за относительно короткое время.
В последние десятилетия применение эволюционных методов пользуется все возрастающей популярностью, особенно в сочетании с нейросетями и нечеткой логикой.
Популярным приложением генетических алгоритмов является оптимизация многопараметрических функций. Многие реальные задачи могут быть сформулированы как поиск оптимального значения, где значение - сложная функция, зависящая от некоторых входных параметров. В некоторых случаях, представляет интерес найти те значения параметров, при которых достигается наилучшее точное значение функции. Часто, точный оптимум не требуется - решением может считаться любое значение, которое лучше некоторой заданное величины. В этом случае, генетические алгоритмы - часто наиболее приемлемый метод для поиска хороших значений. Сила генетического алгоритма заключена в его способности манипулировать одновременно многими параметрами, эта особенность ГА использовалось в сотнях прикладных программ, включая проектирование самолетов, настройку параметров алгоритмов и поиску устойчивых состояний систем нелинейных дифференциальных уравнений.
Считается, что для реальных задач имеющих точные решения, однозначно получаемые численными методами, генетические алгоритмы не должны применяться. Как правило, это делается в учебных (тестовых) целях для проверки правильности реализации.
Программа предназначена для решения задачи многокритериальной оптимизации функций многих переменных. Оптимизация производится с помощью генетического алгоритма; также возможно применение алгоритма Нелдера-Мида для уточнения полученных решений. Генетический алгоритм глобальной оптимизации со стратегией турнира, элитизмом, кроссовером и мутациями. Не требует производных первого и более высоких порядков. Функция должна быть определена на всей задаваемой области. С высокой вероятностью находит глобальный минимум независимо от характера функции, количества локальных минимумов и величины области определения. Алгоритм стремится максимизировать целевые функции. Время, затрачиваемое на работу алгоритма, зависит от количества и сложности целевых функций, количества переменных и настроек алгоритма.
Назначение кнопок:
1. Кнопка "Расчет" запускает алгоритм оптимизации, используя введенные данные и настройки.
2. Кнопка "Параметры" вызывает окно настроек.
Назначение полей:
1. Поле "Имя переменной" содержит имя одной из переменных, образующих пространство поиска. От этих переменных зависят целевые функции.
2. Поля "Нижняя граница определения" и "Верхняя граница определения" содержат соответствующие границы интервалов, в которых находятся значения переменных.
3. Поле "Имя целевой функции" содержит имя одной из оптимизируемых целевых функций.
4. Поля "Нижняя граница требований" и "Верхняя граница требований" содержат соответствующие границы интервалов, в которых пользователь желает видеть значения целевых функций в решении.
5. Поле "Весовой коэффициент" содержит весовые коэффициенты, выражающие неравнозначность целевых функций.
1. Во все поля, кроме полей для названий переменных и полей для целевых функций, можно вводить только числа.
2. Разделяющий знак для десятичных долей - точка; например: 3.14.
3. Нижние границы должны быть меньше верхних.
4. Названия переменных должны быть набраны в нижнем регистре.
5. Верхние границы требований к критериям не могут быть равны нулю.
6. Переменные, используемые в зависимостях, должны совпадать с заявленными.
7. Аргументы функций должны быть в круглых скобках.
8. Весовые коэффициенты должны быть больше или равны единице.
Форма выглядит следующим образом:
После завершения расчёта в нижней части будут выведен результат:
Ссылка “Возврат на один уровень вверх” осуществляет переход на предыдущую страницу.