В оптимизации колонии муравьев (ACO), мета-эвристическая колония искусственных муравьев участвует в обнаружении хороших решений трудных дискретных проблем оптимизации. Сотрудничество - ключевой компонент проекта алгоритмов ACO: выбор состоит в том, чтобы выделить вычислительные ресурсы ряду относительно простых агентов (искусственные муравьи), которые косвенно связаны со стигмержи. Хорошие решения возникают на стадии становления совместного взаимодействия агентов.
У искусственных муравьев есть двойная природа. С одной стороны они - абстракция тех поведенческих черт реальных муравьев, которые, казалось, были в основе поведения обнаружения кратчайшего пути, наблюдаемого в реальных колониях муравьев. С другой стороны они были обогащены некоторыми возможностями, которыми не обладают естественные копии. Фактически, мы хотим, чтобы оптимизация колонии муравьев была техническим подходом к разработке и реализации систем программного обеспечения для решения трудных проблем оптимизации. Поэтому разумно дать искусственным муравьям некоторые возможности, которые, не соответствуют некоторым возможностям их реальных коллег муравьев, сделать их более эффективными и действенными. В дальнейшем мы обсудим характеристики природы искусственных муравьев, и чем они отличаются от реальных муравьев.
Большинство идей ACO происходят от реальных муравьев. В частности, используются: (1) колония сотрудничающих особей, (2) (искусственный) след феромона для локальной стигмержи передачи, (3) последовательность локальных перемещений, чтобы счесть кратчайшие пути, и (4) стохастическая политика решения, используя локальную информацию и никакого предвидения.
Колония сотрудничающих особей. Как и реальные колонии муравьев, муравьиные алгоритмы составлены из совокупности, или колонии, из параллельных и асинхронных объектов, глобально сотрудничающих между собой, чтобы найти хорошее "решение" рассматриваемой задачи. Хотя сложность каждого искусственного муравья такова, что он может создать доступное решение (поскольку реальный муравей так или иначе может найти путь между муравейником и едой), высококачественные решения - результат сотрудничества особей целой колонии. Муравьи сотрудничают посредством информации, они одновременно читают и записывают проблемные состояния тех мест, которые они посещают, как объяснено в следующем элементе.
След феромона и стигмержи. Искусственные муравьи изменяют некоторые аспекты своей среды, как это делают реальные муравьи. В то время как реальные муравьи вносят вклад в состояние мира – оставляя химическое вещество, феромон, искусственные муравьи изменяют некоторую числовую информацию, локально хранившую в состоянии проблемы, которую они посещают. Эта информация принимает во внимание текущую историю/производительность муравья и может читаться/записаться любым муравьем, получающим доступ к состоянию. По аналогии мы называем эту числовую информацию искусственным следом феромона, далее кратко о следе феромона. В алгоритмах ACO локальные следы феромона - единственные каналы передачи среди муравьев. Эта стимержи форма общения играет главную роль в использовании коллективного знания. Его основной эффект состоит в том, чтобы изменить способ, которым среда (проблемная среда) локально воспринята муравьями как функция всей предыстории целой колонии муравьев. Обычно, в алгоритмах ACO механизм испарения, подобный реальному испарению феромона, изменяет информацию о феромоне в течение долгого времени. Испарение феромона позволяет колонии муравьев медленно забывать свое прошлое так, чтобы это могло направить свой поиск по новым направлениям, не будучи сверхограниченным прошлыми решениями.
Поиск кратчайшего пути и локальные перемещения. Искусственные и реальные муравьи совместно используют общую задачу: найти кратчайший (минимальная стоимость) путь, соединяющий источник (муравейник) и место назначения (еда). Реальные муравьи не переходят, они только идут через состояния смежного ландшафта, и так же делают искусственных муравьев, двигаясь шаг за шагом через “смежные состояния” проблемы. Конечно, точные определения состояния и смежности специфичны для проблемы.
Стохастическая и ограниченная политика изменения состояния. Искусственные муравьи, как и реальные, создают решения, применяющие вероятностную политику решения для перемещения через смежные состояния. Как и у реальных муравьев, политика искусственных муравьев использует только локальную информацию, и не использует предвидение, чтобы предсказать будущее состояние. Поэтому, примененная политика абсолютно локальна в пространстве и времени. Политика – это функция обоих априорных информаций, представленная проблемными спецификациями (эквивалентная структура ландшафта для реальных муравьев), и локальной модификацией в среде (следа феромона), которая вызвана прошлыми муравьями.
Как мы уже говорили, у искусственных муравьев есть некоторые характеристики, которых нет у их коллег – реальных муравьев.
• Искусственные муравьи живут в дискретном мире и их перемещения состоят из переходов от дискретных состояний до дискретных состояний.
• У искусственных муравьев есть внутреннее состояние. Это частное состояние содержит в памяти муравья прошлые действия.
• Искусственные муравьи вносят такое количество феромона, которое зависит от качества найденного решения.
• Искусственная синхронизация муравьев в наложении феромона - зависимая проблема и часто не отражает реальное поведение муравьев. Например, во многих случаях искусственные муравьи обновляют следы феромона только генерировав решение.
• Чтобы улучшить полную системную эффективность, алгоритмы ACO могут быть обогащены такими дополнительными возможностями как предвидение, локальная оптимизация, отслеживание в обратном порядке, и так далее, который не может быть найден у реальных муравьев. Во многих реализациях муравьи были гибридизированы с локальными процедурами оптимизации, в то время как до сих пор только Мишель и Миддендорф использовали простую функцию предвидения с одним шагом и нет никаких примеров отслеживания в обратном порядке процедур, добавленных к основным возможностям муравья, за исключением простых процедур восстановления, используемых Ди Каро и Дориго.
В следующем разделе мы покажем, как искусственные муравьи могут участвовать в работе на алгоритмической платформе так, чтобы они были применены к дискретным проблемам оптимизации.
В алгоритмах ACO колонии искусственных муравьев с вышеописанными характеристиками вместе ищут качественное хорошее решение проблемы оптимизации рассматриваемой задачи. Каждый муравей создает решение, или его компонент, запускающейся с начального состояния, выбранного согласно некоторой проблеме, обусловленной критериями. При создании его собственного решения каждый муравей собирает информацию относительно проблемных характеристик и относительно его собственной производительности, и использует эту информацию, чтобы изменить представление проблемы, как уже было замечено другими муравьями. Муравьи могут действовать одновременно и независимо, показывая совместное поведение. Они не используют непосредственную связь: это - стигмержи парадигма, которая управляет обменом информацией среди муравьев.
Инкрементный конструктивный подход используется муравьями для поиска дополнительного решение.
Решение выражено как минимальная стоимость (самый короткий путь через состояния проблемы в соответствии с ограничениями проблемы). Сложность каждого муравья такова, что даже один муравей, в состоянии найти (вероятно, низкое качество) решение. Решения высокого качества можно найти только в качестве выходящего результате глобального сотрудничества между всеми агентами колонии, одновременно создающей различные решения.
Согласно присвоенному понятию окрестности (зависимой от проблемы), каждый муравей создает решение, перемещаясь через (конечную) последовательность соседних состояний. Перемещения выбраны путем применения политики стохастического локального поиска ((1) муравьям направлена частная информация (внутреннее состояние муравья, или память) и (2) общедоступен след феромона) и априорно специфичны для проблемы локальной информации.
Внутреннее состояние муравья хранит информацию о прошлом муравья. Это может использоваться, чтобы перенести полезную информацию, чтобы вычислить значение/хорошие качества сгенерированного решения и/или вложить в каждое осуществляемое перемещение. Кроме того это может играть фундаментальную роль, чтобы управлять выполнимостью решений. В некоторых задах, как правило, в комбинаторной оптимизации, некоторые из перемещений доступны муравью в том состоянии, которого может и не существовать. Этого можно избежать, используя память муравья. Муравьи поэтому могут создавать допустимые решения, используя только знания о локальном состоянии и об эффектах действий, которые могут быть выполнены в локальном состоянии.
Локальная, общественная информация включает в себя некоторые проблемы конкретной эвристической информации и знаний, закодированной в следах феромона, накопленных всеми муравьями с начала поискового процесса. На этот раз глобальное знание феромона, составленное муравьями, является совместно используемой локальной долгосрочной памятью, которая влияет на решения муравьев. Решения о том, когда муравьи должны выпустить феромон на "окружающую среду" и сколько феромона должно быть депонировано, зависят от характеристик проблемы и от проекта реализации. Муравьи могут выпустить феромон при создании решения (онлайн шаг за шагом), или после того, как решение было создано, возвращаясь ко всем посещаемым состояниям (онлайн отложенный), или оба. Как мы сказали, автокатализ играет важную роль в функционировании алгоритмов ACO: чем больше муравьев выбирает перемещение, тем больше перемещение вознаграждено (добавляя феромон) и становится более интересным для следующих муравьев. Вообще, количество депонированного феромона сделано пропорционально совершенству решения, которое муравей создал (или создает). Таким образом, если перемещение способствовало генерации высококачественного решения, то его совершенство будет увеличено пропорционально своему вкладу.
Функциональный состав локально доступного феромона и эвристических значений определяет таблицы решений муравья, то есть, вероятностные таблицы, используемые политикой решения муравьев направить их поиск к самым интересным областям пространства поиска. Стохастический компонент политики решения выбора перемещения и ранее обсужденного механизма испарения феромона избегает быстрого дрейфа всех муравьев к той же самой части пространства поиска. Конечно, уровень стохастичности политики и силы обновлений в следе феромона определяет баланс между исследованием новых точек в пространстве состояний и эксплуатацией накопленного знания. В случае необходимости и выполнения политика решения муравьев может быть обогащена специфичными для проблемы компонентами, такими как отслеживание в обратном порядке процедур или предвидения.
Как только муравей выполнил свою задачу, которая состоит из создания решения и внесения информации о феромоне, муравей "умирает", то есть, он удаляется из системы.
Полное мета-эвристическое ACO, по сравнению с двумя вышеописанными компонентами, действующих с локальной точки зрения (то есть, генерация муравьев и испарение феромона), может также включить некоторые дополнительные компоненты, которые используют глобальную информацию и которые называются в алгоритме демонами. Например, демону можно позволить наблюдать за поведением муравьев, и собирать полезную глобальную информацию, чтобы внести дополнительную информацию о феромоне, смещение, в этом случае – процесс поиска муравья с нелокальной точки зрения. Или он может на основе наблюдения за всеми решениями, сгенерированными муравьями, применить специфичные для проблемы локальные процедуры оптимизации и внести дополнительный феромон "офлайн" относительно феромона муравья, депонированного онлайн.
Трем основным деятельностям алгоритма ACO (генерация муравьев, испарение феромона и действия демона), возможно, понадобится некоторая синхронизация. Вообще, строго последовательное планирование действий является особенно подходящим для нераспределенных проблем, где глобальное знание легкодоступно в любой момент, и операции могут удобно синхронизироваться. И напротив, некоторая форма параллелизма может быть легко и эффективно использована в распределенных проблемах, как маршрутизация в сетях связи.
Как указывалось выше, некоторые описанные компоненты и поведения являются дополнительными, такие как действия демона, или строго зависящими от реализации, такие как то, когда и как феромон депонирован. Вообще, онлайновое постепенное обновление феромона и онлайновые задержанные компоненты обновления феромона являются взаимоисключающими, и только в немногих случаях они оба существуют или оба отсутствующие (в случае, они отсутствуют, феромон депонирован демоном).
Алгоритмы ACO, как следствие их параллельного и адаптивного характера, являются особенно подходящими для распределенных стохастических проблем, где присутствие внешних источников определяет нестационарно в представленной задаче (с точки зрения затрат и/или окружающей среды). Например, много проблем, связанных с сетями связи или транспортными сетями, свойственно распределены и неустановленны, и это часто мешает иметь точную модель базовой изменчивости. И напротив, так как стигмержи – единственный коммуникационный метод между муравья, и это пространственно локализовано, алгоритмы ACO могут выполняться не в лучшем случае в случае возникновения проблем, где у каждого состояния есть большой размер окружения. Фактически, у муравья, который посещает состояние большого размера окружения, есть огромное число возможных перемещений, среди которых можно выбрать. Поэтому, вероятность, что много муравьев посетят одно и тоже состояние, является очень маленькой, и следовательно практически нет, если таковые вообще имеются, разницы между использованием или не следами феромона.
In the ant colony optimization (ACO) meta-heuristic a colony of artificial ants cooperate in finding good solutions to difficult discrete optimization problems. Cooperation is a key design component of ACO algorithms: The choice is to allocate the computational resources to a set of relatively simple agents (artificial ants) that communicate indirectly by stigmergy. Good solutions are an emergent property of the agents’ cooperative interaction.
Artificial ants have a double nature. On the one hand, they are an abstraction of those behavioral traits of real ants which seemed to be at the heart of the shortest path finding behavior observed in real ant colonies. On the other hand, they have been enriched with some capabilities which do not find a natural counterpart. In fact, we want ant colony optimization to be an engineering approach to the design and implementation of software systems for the solution of difficult optimization problems. It is therefore reasonable to give artificial ants some capabilities that, although not corresponding to any capacity of their real ants counterparts, make them more effective and efficient. In the following we discuss first the nature inspired characteristics of artificial ants, and then how they differ from real ants.
Most of the ideas of ACO stem from real ants. In particular, the use of: (i) a colony of cooperating individuals, (ii) an (artificial) pheromone trail for local stigmergetic communication, (iii) a sequence of local moves to find shortest paths, and (iv) a stochastic decision policy using local information and no lookahead.
Colony of cooperating individuals. As real ant colonies, ant algorithms are composed of a population, or colony, of concurrent and asynchronous entities globally cooperating to find a good “solution” to the task under consideration. Although the complexity of each artificial ant is such that it can build a feasible solution (as a real ant can find somehow a path between the nest and the food), high quality solutions are the result of the cooperation among the individuals of the whole colony. Ants cooperate by means of the information they concurrently read/write on the problem’s states they visit, as explained in the next item.
Pheromone trail and stigmergy. Artificial ants modify some aspects of their environment as the real ants do. While real ants deposit on the world’s state they visit a chemical substance, the pheromone, artificial ants change some numeric information locally stored in the problem’s state they visit. This information takes into account the ant’s current history/performance and can be read/written by any ant accessing the state. By analogy, we call this numeric information artificial pheromone trail, pheromone trail for short in the following. In ACO algorithms local pheromone trails are the only communication channels among the ants. This stigmergetic form of communication plays a major role in the utilization of collective knowledge. Its main effect is to change the way the environment (the problem landscape) is locally perceived by the ants as a function of all the past history of the whole ant colony. Usually, in ACO algorithms an evaporation mechanism, similar to real pheromone evaporation, modifies pheromone information over time. Pheromone evaporation allows the ant colony to slowly forget its past history so that it can direct its search towards new directions without being over-constrained by past decisions.
Shortest path searching and local moves. Artificial and real ants share a common task: to find a shortest (minimum cost) path joining an origin (nest) to destination (food) sites. Real ants do not jump, they just walk through adjacent terrain’s states, and so do artificial ants, moving step-by-step through “adjacent states” of the problem. Of course, exact definitions of state and adjacency are problem-specific.
Stochastic and myopic state transition policy. Artificial ants, as real ones, build solutions applying a probabilistic decision policy to move through adjacent states. As for real ants, the artificial ants’ policy makes use of local information only and it does not make use of lookahead to predict future states. Therefore, the applied policy is completely local, in space and time. The policy is a function of both the a priori information represented by the problem specifications (equivalent to the terrain’s structure for real ants), and of the local modifications in the environment (pheromone trails) induced by past ants.
As we said, artificial ants have also some characteristics which do not find their counterpart in real ants.
• Artificial ants live in a discrete world and their moves consist of transitions from discrete states to discrete states.
• Artificial ants have an internal state. This private state contains the memory of the ant past actions.
• Artificial ants deposit an amount of pheromone which is a function of the quality of the solution found.
• Artificial ants timing in pheromone laying is problem dependent and often does not reflect real ants behavior. For example, in many cases artificial ants update pheromone trails only after having generated a solution.
• To improve overall system efficiency, ACO algorithms can be enriched with extra capabilities like lookahead, local optimization, backtracking, and so on, that cannot be found in real ants. In many implementations ants have been hybridized with local optimization procedures, while, so far, only Michel and Middendorf have used a simple one-step lookahead function and there are no examples of backtracking procedures added to the basic ant capabilities, except for simple recovery procedures used by Di Caro and Dorigo.
In the following section we will show how artificial ants can be put to work in an algorithmic framework so that they can be applied to discrete optimization problems.
In ACO algorithms a finite size colony of artificial ants with the above described characteristics collectively searches for good quality solutions to the optimization problem under consideration. Each ant builds a solution, or a component of it6, starting from an initial state selected according to some problem dependent criteria. While building its own solution, each ant collects information on the problem characteristics and on its own performance, and uses this information to modify the representation of the problem, as seen by the other ants. Ants can act concurrently and independently, showing a cooperative behavior. They do not use direct communication: it is the stigmergy paradigm that governs the information exchange among the ants.
An incremental constructive approach is used by the ants to search for a feasible solution.
A solution is expressed as a minimum cost (shortest) path through the states of the problem in accordance with the problem’s constraints. The complexity of each ant is such that even a single ant is able to find a (probably poor quality) solution. High quality solutions are only found as the emergent result of the global cooperation among all the agents of the colony concurrently building different solutions.
According to the assigned notion of neighborhood (problem-dependent), each ant builds a solution by moving through a (finite) sequence of neighbor states. Moves are selected by applying a stochastic local search policy directed (i) by ant private information (the ant internal state, or memory) and (ii) by publicly available pheromone trail and a priori problem-specific local information.
The ant’s internal state stores information about the ant past history. It can be used to carry useful information to compute the value/goodness of the generated solution and/or the contribution of each executed move. Moreover it can play a fundamental role to manage the feasibility of the solutions. In some problems in fact, typically in combinatorial optimization, some of the moves available to an ant in a state can take the ant to an infeasible state. This can be avoided exploiting the ant’s memory. Ants therefore can build feasible solutions using only knowledge about the local state and about the effects of actions that can be performed in the local state.
The local, public information comprises both some problem-specific heuristic information, and the knowledge, coded in the pheromone trails, accumulated by all the ants from the beginning of the search process. This time-global pheromone knowledge built-up by the ants is a shared local long-term memory that influences the ants’ decisions. The decisions about when the ants should release pheromone on the “environment” and how much pheromone should be deposited depend on the characteristics of the problem and on the design of the implementation. Ants can release pheromone while building the solution (online step-by-step), or after a solution has been built, moving back to all the visited states (online delayed), or both. As we said, autocatalysis plays an important role in ACO algorithms functioning: the more ants choose a move, the more the move is rewarded (by adding pheromone) and the more interesting it becomes for the next ants. In general, the amount of pheromone deposited is made proportional to the goodness of the solution an ant has built (or is building). In this way, if a move contributed to generate a high-quality solution its goodness will be increased proportionally to its contribution.
A functional composition of the locally available pheromone and heuristic values defines ant-decision tables, that is, probabilistic tables used by the ants’ decision policy to direct their search towards the most interesting regions of the search space. The stochastic component of the move choice decision policy and the previously discussed pheromone evaporation mechanism avoid a rapid drift of all the ants towards the same part of the search space. Of course, the level of stochasticity in the policy and the strength of the updates in the pheromone trail determine the balance between the exploration of new points in the state space and the exploitation of accumulated knowledge. If necessary and feasible, the ants’ decision policy can be enriched with problem-specific components like backtracking procedures or lookahead.
Once an ant has accomplished its task, consisting of building a solution and depositing pheromone information, the ant “dies”, that is, it is deleted from the system.
The overall ACO meta-heuristic, beside the two above-described components acting from a local perspective (that is, ants generation and activity, and pheromone evaporation), can also comprise some extra components which use global information and that go under the name of daemon actions. For example, a daemon can be allowed to observe the ants’ behavior, and to collect useful global information to deposit additional pheromone information, biasing, in this way, the ant search process from a non-local perspective. Or, it could, on the basis of the observation of all the solutions generated by the ants, apply problem-specific local optimization procedures and deposit additional pheromone “offline” with respect to the pheromone the ants deposited online.
The three main activities of an ACO algorithm (ants generation and activity, pheromone evaporation, and daemon actions) may need some kind of synchronization. In general, a strictly sequential scheduling of the activities is particularly suitable for non-distributed problems, where the global knowledge is easily accessible at any instant and the operations can be conveniently synchronized. On the contrary, some form of parallelism can be easily and efficiently exploited in distributed problems like routing in telecommunications networks.
As pointed out above, some described components and behaviors are optional, like daemon activities, or strictly implementation-dependent, like when and how the pheromone is deposited. In general, the online step-by-step pheromone update and the online delayed pheromone update components are mutually exclusive and only in few cases they are both present or both absent (in the case they are absent the pheromone is deposited by the daemon).
ACO algorithms, as a consequence of their concurrent and adaptive nature, are particularly suitable for distributed stochastic problems where the presence of exogenous sources determines a non-stationarity in the problem representation (in terms of costs and/or environment). For example, many problems related to communications or transportation networks are intrinsically distributed and non-stationary and it is often not possible to have an exact model of the underlying variability. On the contrary, because stigmergy is both the only inter-ant communication method and it is spatially localized, ACO algorithms could perform not at best in case of problems where each state has a big-sized neighborhood. In fact, an ant that visits a state with a big-sized neighborhood has a huge number of possible moves among which to choose. Therefore, the probability that many ants visit the same state is very small, and consequently there is little, if any, difference between using or not pheromone trails.