Нейрокомпьютинг и его применения в экономике и бизнесе
Метод муравьиных колоний
Энтомологи установили, что муравьи способны быстро находить кратчайший путь от муравейника к источнику пищи. Более того, они могут адаптироваться к изменяющимся условиям , находя новый кратчайший путь. Рассмотрим рисунок 6.5: муравьи движутся по прямой, соединяющей муравейник с местом, в котором находится пища. При движении муравей метит свой путь специальными веществами - феромонами, и эта информация используется другими муравьями для выбора пути. А именно, муравьи предпочитают тропки наиболее обогащенные феромонами. Это элементарное правило поведения муравьев и определяет их способность находить новые пути, если старый оказывается перерезанным преградой. Действительно, достигнув этой преграды, муравьи уже не смогут продолжить свой путь и с равной вероятностью будут обходить ее справа и слева. То же самое будет происходить и на обратной стороне преграды. Однако, те муравьи, которые случайно выберут кратчайший путь (налево от преграды и направо - на обратном пути), будут быстрее проходить свой путь и он с большей скоростью станет обогащаться феромонами. Поэтому следующие муравьи будут предпочитать именно этот наикратчайший путь, метя его и далее. Очевидная положительная обратная связь быстро приведет к тому, что кратчайший путь станет единственным маршрутом движения насекомых.
Рис. 6.5. Муравьи находят новый кратчайший новый путь (сверху от преграды) который быстрее обогащается феромонами
Подобный процесс может осуществляться и в компьютерном мире, населенном Искусственными Муравьями (ИМ). Такие муравьи могут решить и нашу задачу коммивояжера. В этом случае они движутся от города к городу по ребрам соответствующего графа. При этом они выбирают направление движения, используя вероятностную функцию, зависящую как от предыдущих попыток движения по данному ребру, так и от эвристического значения, являющегося функцией длины ребра. ИМ с большей вероятностью будут предпочитать ближайшие города и города, связанные ребрами, наиболее богатыми феромонами.
Первоначально искусственных муравьев размещаются в случайно выбранных городах. В каждый последующий момент времени они перемещаются в соседние города и изменяют концентрацию феромона на своем пути (локальная модификация). После того, как все ИМ завершат движения по замкнутому маршруту, тот из них, который проделал кратчайший путь, добавляет к его звеньям количество феромона, обратно пропорциональное длине этого пути (глобальная модификация). В отличие от живых муравьев, ИМ обладают способностью определять расстояние до соседних городов и помнят, какие города они уже посетили. Оказывается, метод искусственных муравьиных колоний может давать результаты, лучшие чем при использовании имитации отжига, нейронных сетей, и генетических алгоритмов.
| 1 | 5.86 | 5.88 | 5.98 | 6.06 |
| 2 | 6.05 | 6.01 | 6.03 | 6.25 |
| 3 | 5.57 | 5.65 | 5.70 | 5.83 |
| 4 | 5.70 | 5.81 | 5.86 | 5.87 |
| 5 | 6.17 | 6.33 | 6.49 | 6.70 |
Напомним вновь, что при электронной или оптической реализации нейросетевой подход находится вне конкуренции в ситуациях, когда необходимо очень быстро находить не обязательно оптимальное, но достаточно хорошее решение.
