Нейрокомпьютинг и его применения в экономике и бизнесе


Метод муравьиных колоний


Энтомологи установили, что муравьи способны быстро находить кратчайший путь от муравейника к источнику пищи. Более того, они могут адаптироваться к изменяющимся условиям , находя новый кратчайший путь. Рассмотрим рисунок 6.5: муравьи движутся по прямой, соединяющей муравейник с местом, в котором находится пища. При движении муравей метит свой путь специальными веществами - феромонами, и эта информация используется другими муравьями для выбора пути. А именно, муравьи предпочитают тропки наиболее обогащенные феромонами. Это элементарное правило поведения муравьев и определяет их способность находить новые пути, если старый оказывается перерезанным преградой. Действительно, достигнув этой преграды, муравьи уже не смогут продолжить свой путь и с равной вероятностью будут обходить ее справа и слева. То же самое будет происходить и на обратной стороне преграды. Однако, те муравьи, которые случайно выберут кратчайший путь (налево от преграды и направо - на обратном пути), будут быстрее проходить свой путь и он с большей скоростью станет обогащаться феромонами. Поэтому следующие муравьи будут предпочитать именно этот наикратчайший путь, метя его и далее. Очевидная положительная обратная связь быстро приведет к тому, что кратчайший путь станет единственным маршрутом движения насекомых.

Муравьи находят новый кратчайший новый путь (сверху от преграды) который быстрее обогащается феромонами

Рис. 6.5.  Муравьи находят новый кратчайший новый путь (сверху от преграды) который быстрее обогащается феромонами

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


Начало  Назад  Вперед