Генетические алгоритмы в задачах классификации искусственных нейронных сетей

ОГЛАВЛЕНИЕ

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

•    Скачать демо - 99.6 Кб
•    Скачать исходники - 25.2 Кб

Введение

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

Подготовка

Требуется знание генетических алгоритмов. Для изучения темы посмотрите сайты: генетические алгоритмы, генетическое программирование, генетические алгоритмы на разговорном английском. Необходимо понимание процессов кроссовера, мутации и селекции для грамотного использования кода. Консольный интерфейс для нейронной сети и описание структуры файла находится в предыдущей статье: Искусственные нейронные сети с обратным распространением на C++.

Использование кода

Строка помощи консольного приложения позволяет использовать следующие параметры:

 argv[1] t-train, r-run
 argv[2] network conf file
 argv[3] cls1 files [0.9]
 argv[4] cls2 files [0.1]
 argv[5] epochs num
 argv[6] [population size 50]
 argv[7] [crossover chance 2]
 argv[8] [mutation chance 1000]
  argv[9] [validation class]
  argv[10] [test class]
  argv[12] [validation TH 0.5]
  argv[12] [validation type [mse]]
 argv[13] [normalization]: [0-no], 1-minmax, 2-zscore,
                            3-softmax, 4-energy
 argv[14] [error tolerance cls] +- 0.05 default

 argv[1] r-run
 argv[2] network conf file
 argv[3] cls files
 argv[4] [validation TH 0.5]
 argv[5] [normalization]: [0-no], 1-minmax, 2-zscore, 3-softmax, 4-energy

 ann1dn.exe t net.nn cls1 cls2 3000 [50]
            [crossover rate] [mutation rate]
            [tst.txt][val.txt][TH [0.5]][vtype [mse]]
            [normalization [0]] [err [0.05]]
 ann1dn.exe r net.nn testcls [TH [0.5]] [normalization [0]]

Единственным отличием от проекта искусственная нейронная сеть с обратным распространением на C++ является добавление специфичных параметров GA: 6, 7 и 8. В остальном все такое же. Они обозначают начальный размер популяции, вероятность кроссовера и вероятность мутации. Стандартные значения - 50, 2 и 1000. Частоты кроссовера и мутации означают, что есть шанс 1 из 2 для кроссовера генов для каждой хромосомы двух родителей, и вероятность мутации равна 1 из 1000 для мутации определенных битов гена в ходе процесса спаривания. Итак, можно начать обучение прямо сейчас:

>ann1dg.exe t iris.nn setosa.txt virgi.txt 200

В приложенном файле run.bat находится следующая строка команды для выполнения:

>ann1dg.exe t iris.nn setosa.txt virgi.txt 200   50 2 100  void void 0.5 0   2

Она использует размер популяции 50 организмов, с вероятностью кроссовера, равной 2, и вероятностью мутации, равной 100. Следующие параметры означают случайный отбор контрольной и тестовой выборок из обучающей выборки с использованием среднеквадратичной ошибки в качестве показателя перекрестной проверки и нормализацию Zscore входных данных. Нормализация необходима, если диапазон данных сильно отличается от предпочтительного диапазона; от -1.0 до 1.0 подходит для классификации нейронной сети.

Ниже представлен типичный процесс GA для классификации данных IRIS до setosa и versi от видов virgi:

loading data...
 cls1: 100  cls2: 50  files loaded.  size: 4 samples
 validaton size: 25 12
 validaton size: 26 13
normalizing zscore...
training...
  epoch: 1   0.454 0.450   pop age:0 mean[0.00] fit:0.00
  bOrg: 0.715 0.546  fit 9.68 age 0
  epoch: 2   0.642 0.631   pop age:1 mean[1.00] fit:238.01
  bOrg: 0.715 0.546  fit 9.68 age 1
  epoch: 3   0.630 0.617   pop age:2 mean[1.64] fit:334.49
  bOrg: 0.665 0.341  fit 11.63 age 0
  epoch: 4   0.638 0.617   pop age:3 mean[2.18] fit:288.08
  bOrg: 0.665 0.341  fit 11.63 age 1
  epoch: 5   0.607 0.577   pop age:4 mean[2.48] fit:395.51
  bOrg: 0.665 0.341  fit 11.63 age 2
  epoch: 6   0.636 0.602   pop age:5 mean[2.90] fit:456.78
  bOrg: 0.685 0.341  fit 11.80 age 0
  epoch: 7   0.638 0.583   pop age:6 mean[3.34] fit:390.31
  bOrg: 0.677 0.452  fit 12.09 age 0
  epoch: 8   0.651 0.562   pop age:7 mean[3.52] fit:425.81
  bOrg: 0.764 0.513  fit 12.71 age 0
  epoch: 9   0.649 0.535   pop age:8 mean[3.45] fit:415.64
  bOrg: 0.826 0.455  fit 17.96 age 0
  epoch: 10   0.608 0.445   pop age:9 mean[3.02] fit:408.99
  bOrg: 0.826 0.455  fit 17.96 age 1   vld: 9.71 (epoch 10) se:68.00 sp:100.00 ac:78.38
  epoch: 11   0.650 0.445   pop age:10 mean[2.98] fit:463.34
  bOrg: 0.826 0.455  fit 17.96 age 2   vld: 9.71 (epoch 10) se:68.00 sp:100.00 ac:78.38
  epoch: 12   0.615 0.405   pop age:11 mean[3.24] fit:467.19
  bOrg: 0.826 0.455  fit 17.96 age 3   vld: 9.71 (epoch 10) se:68.00 sp:100.00 ac:78.38
  epoch: 13   0.666 0.454   pop age:12 mean[2.98] fit:532.92
  bOrg: 0.826 0.455  fit 17.96 age 4   vld: 15.42 (epoch 13) se:88.00 sp:100.00 ac:91.89
  epoch: 14   0.662 0.401   pop age:13 mean[3.19] fit:627.14
  bOrg: 0.826 0.455  fit 17.96 age 5   vld: 15.42 (epoch 13) se:88.00 sp:100.00 ac:91.89
  epoch: 15   0.667 0.390   pop age:14 mean[3.35] fit:517.49
  bOrg: 0.711 0.216  fit 22.49 age 0   vld: 15.42 (epoch 13) se:88.00 sp:100.00 ac:91.89
  epoch: 16   0.662 0.372   pop age:15 mean[3.08] fit:508.93
  bOrg: 0.711 0.216  fit 22.49 age 1   vld: 15.42 (epoch 13) se:88.00 sp:100.00 ac:91.89
  epoch: 17   0.638 0.339   pop age:16 mean[2.65] fit:732.92
  bOrg: 0.711 0.216  fit 22.49 age 2   vld: 15.42 (epoch 13) se:88.00 sp:100.00 ac:91.89
  epoch: 18   0.676 0.366   pop age:17 mean[3.27] fit:793.93
  bOrg: 0.711 0.216  fit 22.49 age 3   vld: 33.02 (epoch 18) se:100.00 sp:100.00 ac:100.00
  epoch: 19   0.648 0.333   pop age:18 mean[3.35] fit:741.40
  bOrg: 0.711 0.216  fit 22.49 age 4   vld: 33.02 (epoch 18) se:100.00 sp:100.00 ac:100.00
 
  ...
  ...
 
  epoch: 187   0.747 0.213   pop age:186 mean[1.85] fit:2343.14
  bOrg: 0.778 0.243  fit 42.80 age 0   vld: 65.97 (epoch 183) se:100.00 sp:100.00 ac:100.00
  epoch: 188   0.747 0.213   pop age:187 mean[2.23] fit:1630.09
  bOrg: 0.778 0.243  fit 42.80 age 1   vld: 65.97 (epoch 183) se:100.00 sp:100.00 ac:100.00
  epoch: 189   0.747 0.213   pop age:188 mean[2.17] fit:2050.81
  bOrg: 0.778 0.243  fit 42.80 age 2   vld: 65.97 (epoch 183) se:100.00 sp:100.00 ac:100.00
  epoch: 190   0.748 0.214   pop age:189 mean[2.36] fit:1899.64
  bOrg: 0.778 0.243  fit 42.81 age 0   vld: 65.97 (epoch 183) se:100.00 sp:100.00 ac:100.00
  epoch: 191   0.751 0.217   pop age:190 mean[2.41] fit:1692.95
  bOrg: 0.778 0.243  fit 42.81 age 1   vld: 65.97 (epoch 183) se:100.00 sp:100.00 ac:100.00
  epoch: 192   0.752 0.223   pop age:191 mean[2.00] fit:1869.26
  bOrg: 0.778 0.243  fit 42.81 age 0   vld: 65.97 (epoch 183) se:100.00 sp:100.00 ac:100.00
  epoch: 193   0.755 0.221   pop age:192 mean[2.00] fit:1965.02
  bOrg: 0.778 0.243  fit 42.82 age 0   vld: 81.72 (epoch 193) se:100.00 sp:100.00 ac:100.00
  epoch: 194   0.762 0.227   pop age:193 mean[2.42] fit:2118.48
  bOrg: 0.778 0.243  fit 42.82 age 1   vld: 81.72 (epoch 193) se:100.00 sp:100.00 ac:100.00
  epoch: 195   0.766 0.232   pop age:194 mean[2.63] fit:2538.75
  bOrg: 0.778 0.243  fit 42.82 age 2   vld: 81.72 (epoch 193) se:100.00 sp:100.00 ac:100.00
  epoch: 196   0.778 0.244   pop age:195 mean[2.66] fit:2140.18
  bOrg: 0.778 0.243  fit 42.82 age 3   vld: 81.77 (epoch 196) se:100.00 sp:100.00 ac:100.00
  epoch: 197   0.778 0.243   pop age:196 mean[2.86] fit:2140.25
  bOrg: 0.778 0.243  fit 42.82 age 4   vld: 81.77 (epoch 196) se:100.00 sp:100.00 ac:100.00
  epoch: 198   0.778 0.243   pop age:197 mean[2.76] fit:2311.59
  bOrg: 0.778 0.243  fit 42.82 age 0   vld: 81.81 (epoch 198) se:100.00 sp:100.00 ac:100.00
  epoch: 199   0.778 0.243   pop age:198 mean[2.52] fit:2226.04
  bOrg: 0.778 0.243  fit 42.82 age 1   vld: 81.81 (epoch 198) se:100.00 sp:100.00 ac:100.00
  epoch: 200   0.777 0.242   pop age:199 mean[2.49] fit:1583.92
  bOrg: 0.778 0.243  fit 42.82 age 2   vld: 81.81 (epoch 198) se:100.00 sp:100.00 ac:100.00
training time: 00:00:00:781

classification results: maxacur.nn
 
 train set: 49 25
   sensitivity: 97.96
   specificity: 96.00
   +predictive: 97.96
   -predictive: 96.00
      accuracy: 97.30
 
 validation set: 25 12
   sensitivity: 100.00
   specificity: 100.00
   +predictive: 100.00
   -predictive: 100.00
      accuracy: 100.00
 
 test set: 26 13
   sensitivity: 88.46
   specificity: 100.00
   +predictive: 100.00
   -predictive: 81.25
      accuracy: 92.31

Вывод одиночной эпохи означает для примера последней эпохи 200: средний результат 0.777 популяции на обучающей выборке для позитивного класса, 0.242 – для негативного класса, возраст популяции – 199, средний возраст организмов – 2.49, средняя приспособленность –  1583.92 (обратная от MSE), bOrg – наиболее приспособленный организм с средним результатом 0.788 на обучающей выборке для позитивного класса, 0.243 – для негативного, с возрастом 2, и своими результатами классификации на контрольной выборке.

Для сравнения было выполнено несколько итераций обучения GA, со случайными частями обучающих данных IRIS, и была взята лучшая конфигурация частоты классификации. То же самое было повторено для нейронной сети с алгоритмом обучения с обратным распространением из статьи: Искусственные нейронные сети с обратным распространением на C++. Ниже представлены веса и частоты классификации сети. Видно, что GA достиг очень близких результатов по производительности в сравнении с алгоритмом обратного распространения:

Результаты GA:

4
4 3 2 1

0
1

-44.000000 0.115305
-22.000000 0.257352
-10.000000 0.057181
-1.000000 0.136029

-1.018195
1.106349
-0.252558
-3.816144
0.060086
2.665148
0.106655
-0.719681
1.192948
-2.096924
-0.999024
0.572130
-1.355700
0.017045
1.615307

-2.008180
-8154.750000
-0.141530
7.478271
-1.202083
0.817744
1.999939
-2.613441

-0.727891
-1.999817
14.607610

 train set: 49 25
   sensitivity: 100.00
   specificity: 100.00
   +predictive: 100.00
   -predictive: 100.00
      accuracy: 100.00
 
 validation set: 25 12
   sensitivity: 100.00
   specificity: 100.00
   +predictive: 100.00
   -predictive: 100.00
      accuracy: 100.00
 
 test set: 26 13
   sensitivity: 96.15
   specificity: 100.00
   +predictive: 100.00
   -predictive: 92.86
      accuracy: 97.44

Результаты алгоритма обратного распространения:

4
4 3 2 1

0
1

-43.000000 0.109332
-23.000000 0.251434
-11.000000 0.055665
-1.000000 0.133365

7.644542
1.920880
0.046209
-4.151631
-2.031714
-8.133764
1.372707
-1.903027
2.587456
2.505832
1.232619
-0.139417
0.577583
1.139807
1.212673

-1.549961
-4.962042
4.220874
-1.322594
1.052067
2.433295
-2.301689
0.902922

0.755153
-4.881694
2.221259

 train set: 49 25
   sensitivity: 97.96
   specificity: 100.00
   +predictive: 100.00
   -predictive: 96.15
      accuracy: 98.65
 
 validation set: 25 12
   sensitivity: 100.00
   specificity: 100.00
   +predictive: 100.00
   -predictive: 100.00
      accuracy: 100.00
 
 test set: 26 13
   sensitivity: 100.00
   specificity: 100.00
   +predictive: 100.00
   -predictive: 100.00
      accuracy: 100.00
Читайте также:
  • Манипулирование цветами в .NET – часть первая
    • Скачать демонстрационный проект (.NET 1.1) - 58.8 Кб• Скачать исходники C# (.NET 1.1) - 110.0 Кб• Скачать исходники C# (.NET 2.0) - 111.2 Кб• Скачать исходники VB (.NET 2.0) - 115.7 Кб Введение Почему статья о "цветах"? На самом деле, в .NET, можно использовать только два формата цвета: цвет...
  • Назад к основам – обобщенные структуры данных и алгоритмы в .NET 2.0
    •    Скачать исходники - 265.8 Кб (с тестами NUnit)•    Скачать двоичные файлы - 40.5 Кб•    Домашняя страница проекта NGenerics (CodePlex)Статья не дает все подробности и полные описания внутреннего устройства этих коллекций и алгоритмов - наоборот, она дает ссылки на имеющиеся в интернете ресурс...
  • Определение цен барьерных опционов с помощью сеток. Часть первая – постоянные барьеры
    •    Скачать демонстрационный проект - 5.26 Кб•    Скачать исходники - 12.2 Кб Введение Стоит отметить, что представленный метод можно расширить до вмещения опционов с несколькими постоянными барьерами. После изучения простого примера перейдем к более сложным опционам с изменяющимися во времени ...
  • FuzzyAdvisor – простая экспертная система с нечеткой логикой на F#
    •    Скачать исходники - 108 Кб Введение Более 15 лет назад разрабатывали проект (Brulé и др., 1995), требовавший экспертную систему, выбирающую подходящий вариант исходя из некоторых основных параметров. Были опробованы несколько подходов, в том числе использование исчисления предикатов (...
  • Нейронные сети на C#
    •    Скачать исходники - 251 Кб•    Скачать демонстрационный проект - 181 Кб Введение История нейронных сетей начинается в 1950-х гг., когда была представлена архитектура простейших нейронных сетей. После начальной работы в области идея нейронных сетей стала весьма популярной. Но затем область...