Задачи, решаемые с помощью генетических алгоритмов

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

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

Математическая постановка задачи оптимизации

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

Нельзя отождествлять критерий (критерии) оптимальности и целевую функцию.

Целевая функция — это аналитическая зависимость между критерием (критериями) оптимальности и подлежащими оптимизации параметрами с указанием направления экстремума.

Отличие понятий «критерий» и «целевая функция» состоит в следующем:

• 1. Целевая функция может включать в себя более одного критерия.
• 2. Для целевой функции всегда и обязательно указывается вид экстремума:

Различают два вида задач оптимизации:

• o Задачу минимизации.
• o Задачу максимизации.

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

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

В общем виде находится именно вектор, т.к., например, при решении двухпараметрической задачи, он будет включать в себя два параметра, трехпараметрической — три параметра и т. д.