докладик (Доклад - Генетические алгоритмы, распознавание изображений)

Генетические алгоритмы, распознавание изображений

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

Разберем устройство одного из таких алгоритмов на примере распознавания простейшего изображения. Оперировать мы будем популяциями хромосом (особей), так как алгоритм является итеративным, номер текущей итерации назовем текущей эпохой. Перед составлением алгоритма определим, что же будет являться нашей задачей, и что будет являться её решением: Рассмотрим пример нахождения коэффициентов, в уравнении параболы, исходя из нарисованного от руки изображения. В этом случае задача – найти такие коэффициенты, при которых парабола будет максимально точно совпадать с рисунком, решение задачи – набор из трех коэффициентов в уравнении параболы.

Алгоритм предусматривает популяцию неких объектов (хромосом), которые будут бороться за выживание. Итак,

Хромосома – это возможное решение нашей задачи, не важно какое, правильное или нет.

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

Популяция – набор хромосом текущей эпохи.

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

Кроссовер отвечает за передачу признаков родителей своим потомкам, в самой простой реализации он создаёт новую хромосому из генов двух родителей, «донор» очередного гена выбирается произвольным образом.

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

Fitness-функция: Как и в жизни – не приспособленные виды должны погибать, «чистить» нашу популяцию будет последняя функция, называемая функцией приспособления, или Fitness-функцией. Для каждой хромосомы эта функция возвращает число, обратно пропорциональное «приспособленности» этой хромосомы, на нее накладываются условия: Значение Fitness от идеального решения = 0

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

Теперь можно сформулировать вариант алгоритма

1. Обозначить номер эпохи = 0, создать популяцию хромосом, в генах которых будет произвольная, не противоречащая задаче, информация

2. Посчитать приспособленность популяции

3. Выбрать из популяции особь А

4. С вероятностью P(скрещивания) выбрать особь B и применить оператор кроссовера, результирующую особь занести в новую популяцию.

5. С вероятностью P(мутации) выполнить мутацию произвольной особи, результирующую особь занести в новую популяцию

6. Выполнить операции 3,4,5 n раз, где n >= размера популяции

7. Создать новую популяцию из лучших особей существующей и только что сформированной популяции

8. Увеличить номер текущей эпохи

9. Если результат работы удовлетворителен – остановка алгоритма, иначе – переход к шагу 2.

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

public class Chromosome : IComparable

{

public double[] gens;

static Random random = new Random();

public Chromosome()

{

this.gens = new double[3];

for (int i = 0; i < 3; i++)

{

this.gens[i] = random.NextDouble() * 100;

}

this.fit = fitness(this);

}

public int CompareTo(object obj)

}

Значение 100 выбрано для примера, это не ограничит общности, даже если искомая парабола будет иметь кофээфициенты >100. Отметим метод CompareTo, позволяющий нам сортировать списки объектов Chromosome.

public class Population

{

Random random = new Random();

public List<Chromosome> population;

public int count;

public double crossProbability;

public double MutationProbability;

public int age;

public Population()

{

for (int i = 0; i < 5000; i++)

{

this.population.Add(new Chromosome());

}

}

public void GoToNextGeneration()

{

Chromosome chromosome;

for (int i = 0; i < count; i++)

{

chromosome = population[i];

if (random.NextDouble() < crossProbability)

{

population.Add(Cross(chromosome,population[random.Next(count)]));

}

}

for (int i = 0; i < population.Count; i++)

{

if (random.NextDouble() < MutationProbability)

{

population.Add(Mutate(population[i]));

}

}

population.Sort();

population.RemoveRange(count,population.Count-count);

age++;

}

Chromosome Cross(Chromosome a, Chromosome b)

Chromosome Mutate(Chromosome a)

double Fitness(Chromosome a)

}

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

Второй шаг – мутация, было бы логично мутировать саму хромосому, а не добавлять мутировавший клон, но в этом случае мы теряем содержащееся в исходной хромосоме решение, а оно может быть лучшим в популяции. Наконец, в конце мы сортируем всю нашу получившуюся популяцию по возрастанию Fitness функции, (следовательно – по убыванию правильности решения) удаляем наименее «приспособленные» хромосомы, и увеличиваем номер текущей эпохи.

Давайте рассмотрим, что же представляют собой три последние функции, производящий операции над нашими хромосомами?

Chromosome Cross(Chromosome a, Chromosome b)

{

double[] pair = new double[3];

for (int i = 0; i < 3; i++)

{

if ((random.Next() % 2) == 0)

{

pair[i] = a.Gens[i] + (b.Gens[i] - a.Gens[i]) * 0.1;

}

else

{

pair[i] = b.Gens[i] - (b.Gens[i] - a.Gens[i]) * 0.1;

}

}

Chromosome result = new Chromosome(pair);

return result;

}

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

Поправка (b.Gens[i] — a.Gens[i]) * 0.1 сделана чтобы как-то разнообразить популяцию новыми генотипом.

Chromosome Mutate(Chromosome a)

{

double[] pair = (double[])a.Gens.Clone();

int geneNum = random.Next(3);

pair[geneNum] = random.NextDouble() * 100;

return new Chromosome(pair, a.chromosomeSettings);

}

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

double GetFitness(Chromosome a)

{

double result = 0;

double temp;

for (int i = 0; i < funcLength; i++)

{

temp = Math.Abs(Func(i, a.Gens) - funcArray[i]);

result += temp;

}

return result;

}

double Func(double x, double[] gens)

{

double result = 0;

for (int i =2; i >= 0; i--)

{

result += gens[2-i] * Math.Pow(x, i);

}

return result;

}

Массив funcArray получается сканированием картинки снизу вверх по столбцам, каждый столбец – индекс массива, высота первой найденной черной точки в столбце – значение.
Функция Func – возвращает значение уравнения 2й степени в точке x, с коэффициентами из массива gens
Получается Fitness – это сумма «погрешностей», для каждой точки нашей параболы, которая есть на рисунке. Такая функция не имеет единственный минимум, но, тем не менее, обеспечивает достаточную сходимость алгоритма.

Результат:

При количестве хромосом в популяции = 5000, на 25ом поколении мы получаем достаточно близкое сходство.

Данный алгоритм можно расширить на кривые любого порядка