Article Preview
TopIntroduction
This paper proposes the use of swarm intelligence to solve an allocation problem. In many industrial contexts, allocation problems arouse a great interest in the operational research community. How to share available resources among a set of agents and how to optimise its use are the main considerations of the allocation problem. Although the resource allocation problem can be solved with a variety of techniques, it is still a challenging problem that requires further studies, especially when it diverts to unusual forms. Here we consider a resource allocation problem in hard-constrained environment.
In order to optimise the use of a set of agents in the resource allocation problem, we explore a well-known method of swarm intelligence: Discrete Particle Swarm Optimisation (DPSO). Over the last few decades, numerous scientists have been inspired by the modelling of social interactions of animals to solve NP-hard optimization problems. Even though the communication among the different agents is limited to an exchange of basic information, it results in a very effective team work. For example, in a fish school, each fish shares information with a small number of neighbours, those at its left and right sides and ahead of it. Knowing the movement of the neighbours is the simple information upon which a fish school bases its strategy to avoid predators. As an isolated individual, a fish may, or may not, have the ability to escape a predator, depending on the context. As a member of a group, the fish makes up a collective intelligence that reduces its vulnerability. The aim of the creators of PSO method (Kennedy & Eberhart, 1997) was to reproduce this social interaction among agents in order to solve combinatorial problems.
While PSO provides efficient and satisfactory solutions like other meta-heuristic methods, it also enables to solve many problems with more accurate results than traditional methods, like Genetic Algorithms (GA) (Badamchizadeh & Madani, 2010; Eberhart & Shi, 1998; Liaoa, Tsengb, & Luarnb, 2007) .
Initially, the PSO was developed to solve optimal problems in a continuous space. It was later adapted to solve problems in a discrete space of solutions (Kennedy & Eberhart, 1997; Al-kazemy & Mohan, 2000; Clerc, 2004; Yin, 2004; Badamchizadeh & Madani, 2010; Ho, Jian, & Lin, 2010; Liaoa, Tsengb, & Luarnb, 2007; Liu, Wang, Ding, & Gao, 2010; Yare & Venayagamoorthy, 2007). Miranda and Fonseca (2002) proposed a combination of the particle swarm optimization and evolutionary principle in which an evolutionary process creates new particles. Chio, Chio, and Giacobini (2008) used the evolutionary game to improve the classical PSO. They implemented this approach into the classical Prisoner dilemma to determine the next move of the particles according to the outcome at the previous iteration. The original idea to integrate the evolutionary games with the particle swarm optimization is from Liu and Wang (2008) where a particle swarm optimizer is designed using replicator dynamics of evolutionary games. In this approach, each particle was considered as one player, where the next move is determined according to the replication process given by the replicator dynamics (the principle of the replicator is described later in this document).
The proposed algorithm in this paper is devised based on the idea of integrating PSO with Evolutionary Game Theory (EGT). However, the utilisation of EGT to improve the performance of the classical PSO in the proposed method differs from the other approaches. In Chio, Chio, and Giacobini (2008) and Liu and Wang (2008) the particles are trying to increase their fitness without any consideration of the rest of the swarm but the possible interactions. Unlike these approaches, the combination of EGT and PSO process described in this paper enables to find the optimal weight of the coefficients considering the entire swarm fitness instead of focusing on the individual welfare of the particles themselves. In considering the whole set of the particles, the best global strategy for the swarm is adopted. Each particle accepts decrease of the individual welfare, as long as it enables improvement of the global fitness of the total swarm.