автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.17, диссертация на тему:Доменная модель нейронной сети и ее применение в задачах оптимизации

Глава 1. Введение

§ 1. Актуальность темы.

§ 2. Нейронная сеть Хопфилда и задача оптимизации.

§ 3. Цели и задачи диссертационной работы.

Глава 2. Доменная модель нейронной сети

§ 1. Описание модели.

§ 2. Распознающая способность доменной модели.

§ 3. Число устойчивых состояний доменной сети.

§ 4. Скорость работы доменного алгоритма.

§ 5. Выводы.

Глава 3. Доменная модель в задачах оптимизации.

§ 1. Предпосылки применения доменной модели в задачах оптимизации.

§ 2. Описание эксперимента.

§ 3. Результаты эксперимента.

§ 3.1. Матрицы с разреженным спектром.

§ 3.2. Матрицы со смешанным спектром.

§ 3.3. Матрицы со сплошным спектром.

§ 3.4. Обсуждение результатов.

§ 4. Выводы.

Глава 4. Вероятность обнаружения локальных минимумов в задачах оптимизации.

§ 1. Обобщенная модель Хопфилда.

§ 2. Размер области притяжения.

§ 3. Объем памяти обобщенной модели.

§ 4. Энергия локального минимума.

§ 5. Вероятность обнаружения минимума.

§ 6. Выводы.

§1. Актуальность темы

Теория искусственных нейронных сетей (ИНС) - одна из областей математики, существующая уже более полувека и активно развивающаяся по настоящее время. Одним из важных применений ИНС является решение задач оптимизации [1,2,3], особенно тех из них, которые не могут быть решены точными детерминистическими методами [4-7], а также решение iVP-полных задач [8].

Основной моделью нейронной сети, с помощью которой решаются такие оптимизационные задачи, является модель Хопфилда [9], предложенная в 1982 году. Эта циклическая нейронная сеть, в ходе функционирования меняет свое состояние, понижая при этом значение некоего функционала, называемого энергией, и конвергирует в состояние соответствующее минимуму. Это свойство сети активно используется для случайного поиска оптимального решения: сеть произвольным образом инициализируется (выбирается случайное начальное состояние сети) и затем она, в результате функционирования согласно ее динамической процедуре, переходит в какой-либо локальный минимум энергии. Поскольку наиболее оптимальное решение задачи заранее неизвестно, то описанная процедура случайного поиска повторяется много раз. После большого числа стартов из найденных решений выбирается наиболее оптимальное, т.е. выбирается конфигурация, соответствующая наиболее оптимальному значению функционала. К сожалению, специфика модели такова, что в процессе поиска она имеет тенденцию сходиться к неглубоким локальным минимумам. Кроме того, реализация алгоритма показывает, что время, затрачиваемое на поиск удовлетворительного решения, может оказаться неприемлемо большим.

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

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

§ 6. Выводы

Проведенный анализ показал, что свойства обобщенной модели описываются двумя критическими параметрами г0 и Emin. Первый из них определяет минимальное значение статвеса, при котором образ образует локальный минимум и может быть восстановлен нейронной сетью. Второй — это минимальная глубина локальных минимумов. Существенно, что величины обоих параметров никак не зависят от числа образов М, на которых построена матрица межсвязей. Существенно и то, что удаление из матрицы межсвязей образов, прописанных в матрице межсвязей с статвесами, меньшими критического значения (гт <г0), не влияет на размер объема памяти, однако улучшает ее распознающие характеристики — размер областей притяжения оставшихся образов увеличится и, следовательно, сеть может распознавать более сильно искаженные образы. Вместе с этим, обратим внимание на тот факт, что с ростом размера сети N радиус области притяжения локального минимума уменьшается. Как следует из (4.5), такое уменьшение имеет место даже в том случае, когда загрузка сети с ростом iVлогарифмически уменьшается, как М/N = const/2lnN. Это означает, что с ростом N уменьшается уровень допустимых искажений, при которых сеть способна восстанавливать образы (сеть меньших размеров способна распознавать более сильно искаженные образы).

Во избежание недоразумений следует указать на то, что связь (4.12) между радиусом области притяжения пт и объемом этой области W - W(nm ) существенно нелинейная. Это означает, что даже при очень большом значении радиуса (например пт ~ 0.497/) область притяжения может занимать очень малую часть N -мерного пространства, а доля пространства вне области притяжения с ростом N нарастает экспоненциально и при достаточно больших значениях N стремится к У2.

Действительно, рассмотрим простейший пример - случай стандартной

Л 4 модели Хопфилда (гт =М~ ). На рисунке 4.7 показана зависимость радиуса области притяжения от размерности сети при разных загрузках. Как видно из рис. 4.7а., в случае постоянной загрузки (М/N = const) радиус притяжения с ростом N быстро стремится к нулю. Это соответствует выражению (4.5), из которого следует, что радиус области притяжения заметно отличен от нуля только при небольших размерах сети, когда 2к In N < 1 . Очевидно, что доля пространства, занимаемая всеми М локальными минимумами, в этом случае с ростом N стремится к нулю. В приведенном на рис. 4.76. случае логарифмически уменьшающейся загрузки (М/N = const/21niV) радиус области притяжения с ростом N достаточно быстро уменьшается до некоторого (отличного от нуля) асимптотического значения пт ~ 0.5N(\-4k). Тем не менее, доля пространства, занимаемая всеми М локальными минимумами (величина, равная MW), и в этом случае с ростом N стремится к нулю. Это означает, что с ростом n вероятность нахождения глубоких минимумов при случайном поиске также стремится к нулю.

05 s X tu * к ь s a о n t; ю о о >. s d га

QL

2 ООО 4 ООО 6 ООО

Размер сети N

8 ООО

10 ООО

0.50 о; s х ф е X a re о о >» S 3

Jfc = 0.1 к = 0.5 к= 1 i

2 ООО

4 ООО 6 ООО

Размер сети N

8 ООО

10 ООО

Рис. 4.7. Размер радиуса области притяжения локального минимума в стандартной модели Хопфилда, как функция размерности пространства n для различных значений загрузки сети: а), постоянная загрузка м = ш при к = 0.02, 0.07, 0.1; б), логарифмически уменьшающаяся загрузка м = шп\аЫ при к = 0.1,0.5 ,1.

Необходимо еще раз подчеркнуть, что зависимость "глубже минимум -больше область притяжение — больше вероятность попадания в этот минимум" строго обоснована только в случае корреляционных (хеббовских) матриц. В более общем случае это не зависимость, а скорее экспериментально установленная тенденция, применимая к наиболее глубоким минимумам. Обоснование этой тенденции заключается в том, что любую наперед заданную матрицу можно представить в виде хэббовской матрицы (4.1), построенной на произвольном числе образов (например М-» оо) с произвольными статвесами. И если спектр минимумов функционала, построенного на такой матрице, имеет ярко выраженные минимумы большой глубины, то применительно к ним справедливы сделанные ранее выводы. Трудность наступает в случае, когда таких ярко выраженных минимумов нет и спектр минимумов квазинепрерывен. В этом случае в оптимизационном эксперименте измеряется не вероятность W{E), а частота попадания в минимум с заданной энергией - произведение вероятности на спектральную плотность, характеристики которой неизвестны. Соответственно, затрудняется применение развитой выше теории.

Заключение

В диссертационной работе получены следующие основные результаты.

1. Разработана новая модель нейронной сети - доменная нейронная сеть, спины которой группируются в домены - группы по к жестко связанных спинов в каждой. Показано что, доменная модель обладает в к раз большей емкостью памяти ив к раз большей скоростью работы по сравнению со стандартной моделью Хопфилда.

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

3. Свойства циклической нейронной сети исследованы в наиболее общем случае, когда матрица межсвязей строится по обобщенному правилу Хэбба - образы добавляются в матрицу с статвесами, порождая невырожденный спектр минимумов. Проведен анализ свойств обобщенной модели.

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

1. Papadimitriou С. Н., Steiglitz К.: Combinatorial Optimization. I I Prentice-Hall, Englewood, Cliffs, New Jersey, 1982.

2. Cook W.J., Cunningham W.H., Pulleyblank W.R., and Schrijver A.: Combinatorial Optimization. // J. Wiley & Sons, New York, 1998.

3. Korte В., Vygen J.: Combinatorial Optimization. // Spinger, Berlin and Heidelberg 2000.

4. Таха X. «Введение в исследование операций: в 2-х книгах», кн. 2, перев. с англ., М.: Мир, 1985.

5. Фишер Ф.Н. «Проблемы идентификации в эконометрии». М.: Финансы и статистика, 1978.

6. Forrest S. and Mayer-Kress G.: Genetic algorithms, nonlinear dynamical systems, and models of international security. // Handbook of Genetic Algorithms, Van Nostrand Reinhold, 1991.

7. Davis L.: Applying adaptive algorithms to epistatic domains. // In 9th Int. Joint Conference on AI, 1985.

8. Davis M.D., Sigal R., and Wyuker E.J.: Computability, Complexity and Languages // Academic Press, San Diego 1994.

9. Hopfield J.J.: Neural networks and physical systems with emergent collective computational abilities. // In Proceedings of the National Academy of Sciences USA, 1982, pp. 2554-2558.

10. Takefuji Y., Wang J.: Neural computing for optimization and combinatorics, // Singapore: World Scientific., 1996.

11. П.Хайкин С. «Нейронные сети (Полный курс)», 2-е издание.: Пер. с англ. -М.: Издательский дом "Вильяме"., 2006.

12. Binder К., Young А.Р.: Spin glasses: Experimental facts, theoretical concepts and open questions. // Rev. Mod. Phys. vol. 58, issue 4, 1986, pp. 801-976.

13. Mezard M., Parisi G., and Virasoro M.A.: Spin Glass Theory and Beyond. // World Scientific, Singapore 1987.

14. H.Fisher K.H. and Hertz J.A.: Spin Glasses. // Cambridge University Press, Cambridge 1993.

15. Mydosh J.A.: Spin Glasses: an Experimental Introduction. // Taylor and Francis, London 1993.

16. Hebb D.: The Organization of Behavior. //New York: Wiley, 1949.

17. Palm G., Sommer F.: Information capacity in recurrent McCulloch-Pitts networks with sparsely coded memory states. // Network: Computation in Neural Systems., vol. 3, 1992, pp. 177-186.

18. Hopfield J. J. and Tank D. W.: Neural computation of decisions in optimization problems.//Biological Cybernetics, vol. 52, 1985,pp. 144-152.

19. Hopfield J. J. and Tank D. W.: Computing With Neural Circuits: A Model. // Science, vol. 233,1986, pp. 625-632.

20. Reinelt G.: TSPLIB-A traveling salesman problem library. // ORSA Journal on Computing vol. 3, no. 4, 1991, pp. 376-384.21 .http://www.tsp.gatech.edu/ (Traveling Salesman Problem)

21. Wilson G. V., Pawley G. S.: On the stability of the traveling salesman problem algorithm of Hopfield and Tank. // Biological Cybernetics, vol. 58, 1988, pp. 63-70.

22. Aiyer, S. V. В., Niranjan, M. and Fallside, F.: A theoretical investigation into the performance of the Hopfield model. // IEEE Transactions on Neural Networks, vol. 1,1990, pp. 204-215.

23. Protzel, P. W., Palumbo, D. L. and Arras, M. K.: Performance and fault-tolerance of neural networks for optimization. // IEEE Transactions on Neural Networks, vol. 4,1993, pp. 600-614.

24. Kirkpatrick S., Gelatt C. D., Vecchi M. P.: Optimization by simulated annealing. // Science, vol. 220, 1983, pp 671-680.

25. Rutenbar R.A.: Simulated annealing algorithms: An overview. // IEEE Circuits and Devices Magazine, 1989.

26. Hinton, G., Sejnowski, Т.: Learning and re-learning in boltzmann machines. // In Parallel Distributed Processing: Explorations in The Microstructure of Cognition, MIT Press, Cambridge, chapter 7,1986, pp. 282-317.

27. Tokuda I., Aihara K., and Nagashima Т.: Adaptive annealing for chaotic optimization. // Physical Review E., vol. 58, num 4,1998, pp. 5157-5160.

28. Yamanaka K., Agu M., Miyajima Т.: A continious-time asynchronous BoltsmanMachine. //NeuralNetworks, vol. 10, No. 6, pp. 1103-1107.

29. Glover F. Tabu search: part I. // ORSA J. Сотр. vl, 1989). pp. 190-206.

30. Glover F. Tabu search: part II. // ORSA J. Сотр. v2, 1990). pp. 4-32.

31. Glover F., Laguna. M.: Tabu search. // Boston: Kluwer Acad. Publ. 1997.

32. Glover F.(Ed.) Tabu search methods for optimization. // Feature Issue of Europen J. Oper. Res. vl06,1998, N2-3.

33. Konishi J., Shimba S., Toyama J., Kudo M., Shimbo M.: Tabu search for solving optimization problems on Hopfield neural networks. // Proc. of Third International Conference "Knowledge-Based Intelligent Information Engineering Systems", 1999.

34. Hartwig A., Daske F. and Kobe S.: A recursive branch-and-bound algorithm for the exact ground state of Ising spin-glass models. // Comput. Phys. Commun. vol. 32, 1984, pp. 133-138

35. Klotz Т., Kobe S.: "Valley structures" in the phase space of a finite 3D Ising spin glass with +1 interactions. // J. Phys. A27, 1994, pp. 95-100

36. Klotz Т. and Kobe S.: Exact low-energy landscape and relaxation phenomena in Ising spin glasses. // Act. Phys. Slov. vol. 44, 1994, pp. 347-356

37. Klotz Т., Kobe S.: Cluster structure in the configuration space and relaxation in 3d +1 Ising spin-glass models. // Hayashibara Forum '95. International Symposium on Coherent Approaches to Fluctuations, World Scientific, Singapore, 1996, pp. 192-195

38. Simone C., Diehl M., Junger M., Mutzel P., Reinelt G., and Rinaldi G.,.: Exact ground states of Ising spin glasses: New experimental results with a branch and cut algorithm. // Stat. Phys. 80, 1995, pp. 487-496.

39. Simone C., Diehl M., Junger M., Mutzel P., Reinelt G., and Rinaldi G.: Exact Ground States of Two-Dimensional +-J Ising Spin Glasses. // Stat. Phys. 84, 1996, pp. 1363-1371

40. Rieger H., Santen L., Blasum U., Diehl M., Junger M., Rinaldi G.: The critical exponents of the two-dimensional Ising spin glass revisited: Exact ground-state calculations, Monte Carlo simulations. // J. Phys. A 29, 1996.

41. Palassini M. and Young A.P.: Trivial Ground State Structure in the Two-Dimensional Ising Spin Glass. // Phys. Rev. В 60,1999.

42. Гладков JI.A. B.B. Курейчик, B.M. Курейчик. «Генетические алгоритмы» Издание 2, М., Физматлит, 2006.

43. Еремеев А.В. «Разработка и анализ генетических и гибридных алгоритмов для решения задач дискретной оптимизации». Диссертация кандидата физико-математических наук. Омск, 2000.

44. Aggarwal С. С., Orlin J. В., Tai R. P.: Optimized crossover for maximum independent set. // Oper. Res. v45, 1997, pp. 225-234.

45. Balas E., Niehaus W.: Finding large cliques in arbitrary graphs by bipartite matching. Cliques, coloring, and satisfiability. // DIMACS Ser. Discrete Math. Theoretical Computer Science, vol. 26, 1996, pp 29-49.

46. Balas E., Niehaus W.: Optimized crossover-based genetic algorithms for the maximum cardinality and maximum weight clique problems. // Journal of Heuristics, vol. 4, N 4,1998, pp. 107-122.

47. Boese K. D., Kahng А. В., Muddu S.: A new adaptive multi-start technique for combinatorial global optimizations. // Operations Research Letters, vol. 16, N 2, 1994, pp. 101-114.

48. Bremermann H. J., Roghson J., Salaff S.: Global properties of evolution processes. Natural automata and useful simulations. // London: Macmillan. 1966. pp. 3-42.

49. Eiben A. E., Raue P. E., Ruttkay Zs.: Genetic Algorithms with multiparent recombination. Parallel Problem Solving from Nature III. // Berlin: Springer Verlag, (LNCS), vol. 866, 1994, pp. 78-87.

50. Eremeev A. V.: A genetic algorithm with a non-binary representation for the set covering problem. // Operations Research Proceedings 1998. Berlin: Springer Verlag, 1999, pp. 175-181.

51. Peng M., Gupta N. K., Armitage A. F.: An investigation into the improvement of local minima of the Hopfield network. // Neural Networks vol. 9, N 7, 1996, pp. 1241-1253.

52. Papageorgiou G., Likas A., Stafylopatis A.: Improved exploration in Hopfield network state-space through parameter perturbation driven by simulated annealing. // European Journal of Operational Research, vol. 108, N 2, 1998, pp. 283-292

53. Крыжановский Б.В., Литинский Л.Б. «Отыскание глобального минимума одного многоэкстремального функционала». Искусственный интеллект (2003), т.З, стр. 116-120.

54. Литинский Л.Б., «Нейросетевой подход к задаче минимизации квадратичного Функционала». Искусственный интеллект (2004), т.З. стр. 542-549.

55. Litinskii L., Magomedov В.: Global minimization of a quadratic functional: neural network approach. Pattern Recognition and Image Analysis, v. 15, N1, 2004, pp.80-82.

56. Litinskii L.B.: Eigenvalue problem approach to discrete minimization. // ICANN 2005, Springer-Verlag, Berlin Heidelberg, 2005, pp. 405-410.

57. Вылегжанин Д.В., Литинский Л.Б. «Компьютерная проверка нейросетевого алгоритма дискретной минимизации». Труды второй Всероссийской конференции МСО-2005, М.: МГУ, 2005, стр. 590-596.

58. Вылегжанин Д.В., Литинский Л.Б., Мурашкин А.А. «О выборе стартовых состояний при минимизации квадратичного дискретного функционала». Искусственный интеллект (2005), т.З, стр. 334-342.

59. Крыжановский Б.В., Микаэлян А.Л. «О распознающей способности нейросети на нейронах с параметрическим преобразованием частот». Доклады Академии Наук. 2002. Т. 383, №3, стр. 318-321.

60. Coad P., Nicola J.: Object-Oriented Programming (Textbook Binding). // Pearson Education, 1993.

61. Мейер Б. «Объектно-ориентированное конструирование программных систем». ИНТУИТ.РУ, 2005.

62. Fowler М.: UML Distilled: A Brief Guide to the Standard Object Modeling Language. // Third Edition, Addison-Wesley Professional, 2003

63. Gordon A.: The COM and COM+ Programming Primer. // Prentice Hall PTR, 2000.66. http://msdn.microsoft.com/library/default.asp?url=/library/en-us/dv wrcore/html/wroriautomatingexcelusingexcelobiectmodel.asp (Automating Excel Using the Excel Object Model)

64. Amiit D., Gutfreund H., & Sompolins H.: Spin-glass models of neural networks. // Physical Review A, vol. 32,1986, pp. 1007-1018.

65. Крыжановский Б.В., Магомедов Б.М., Микаэлян А.Л. «Доменная модель нейронной сети». Доклады Академии наук, том. 401, №4, с. 462-466.