[PDF] A Dynamic System Model of Biogeography-Based Optimization

Biogeography-Based Optimization - IEEE Xplore

We discuss natural biogeography and its mathematics, and then discuss how it can be used to solve optimization problems We see that BBO has features in common

[PDF] Biogeography-Based Optimization

Initialize a set of solutions to a problem 2 Compute “fitness” (HSI) for each solution 3 Compute S, ?, and ? for each solution

[PDF] Heuristic Crossover Based on Biogeography-based Optimization

Biogeography based optimization (BBO) is a new evolutionary optimization algorithm based on the science of biogeography for global optimization

[PDF] A NEW BIOGEOGRAPHY-BASED OPTIMIZATION APPROACH

As a modern metaheuristic method, Biogeography-based optimization (BBO) is a generalization of biogeography to evolutionary algorithm inspired on the

[PDF] Biogeography-Based Optimization: A 10-Year Review - ResearchGate

Abstract—Biogeography-based optimization (BBO) is an evolu- tionary algorithm which is inspired by the migration of species between habitats

[PDF] A Dynamic System Model of Biogeography-Based Optimization

Biogeography-based optimization (BBO) is an evolutionary algorithm (EA) morjv ned by the optimality perspective of nat ural biogeography, and was initially

[PDF] Development of a modified biogeography-based optimisation tool

based optimisation (BBO) is a well-known nature-inspired computing metaheuristic Its mechanisms mimic an analogy with biogeography which relates to the

Biogeography-based Optimization (BBO) Algorithm for Single

Biogeography-based optimization (BBO) algorithm for single machine total weighted tardiness problem (SMTWTP) Budi Santosa a , Ade Lia Safitri

[PDF] A Dynamic System Model of Biogeography-Based Optimization

31505_7301544395.pdf C leveland State UniversityEn gagedScholarship@CSU Ele ctrical Engineering & Computer Science Faculty :'1.(&9.4381* (97.(&13,.3**7.3,425:9*7"(.*3(* *5&792*39 A D ynamic System Model of Biogeography-BasedO ptimizationD aniel J. SimonC leveland State University, d .j.simon@csuohio.eduF ollow this and additional works at:-

D58 3,&,)8(-41&78-.5(8:4-.4): 3(%+&(5:'

&794+9-* =3&2.("=89*28422438&

3)9-1

(97.(&1&3)425:9*73,.3**7.3,

422438H

ow does access to this work beneifit you? Let us know!P ublisher's StatementNO

TICE: this is the author's version of a work tha

t was accepted for publication in Applied Sotft

425:9.3,-&3,878:19.3,+7429-5:'1.8-.3,574(888:(-&85**77;.<).9.3,(477(9.4388

97:(9:7&1+472&D.3,&3)49-76:&1.9=(4397412(-&3.8282&=349'7B*(9).39-.8)4(:239

-&3,*82&=-&;*'**32&)*949-.8<4708.3(*.9<&88:'2.D*)+475:'1.(&9.43)*A3.9.;*;*78.43< &88:'8*6:*391=5:'1.8-*).3551.*)"4C425:9.3, / &84( ! *548.947=.9&9.43S imon, Daniel J., "A Dynamic System Model of Biogeography-Based Optimization" (2011).E lectrical Engineering & Computer Science FacultyP ublications. 140. - D58 *3,&,*)8(-41&78-.5(8:4-.4*): *3*(*%+&(5:' @.

879.(1*.8'74:,-994=4:+47+7**&3)453&((8

8'=9-1(97.(&13,.3**7.3,425:97"(.3(5&79239&93,&,)"(-41&78-.5"$9-

&8'**3&((*59*)+47.3(1:8.43.31*(97.(&13,.3**7.3,425:9*7"(.*3(*&(:19= :'1.(&9.438'=&3&:9-47.>*)&)2.3.897&9474+

3,&,*)"(-4

1&78-.5"$47247.3+472&9.4351&8*(439&(91

.'7&7=*8(8:4-.4*):Or iginal CitationD

an Simon. (2011). A dynamic system model of biogeography-based optimization. Applied Sotft Computing, 11(8), 5652-5661, doi:

/ &84( A dynamic system model of biogeography-based optimization"

Dan Simon

University. and Computer United

1. Introduction

Biogeography is [he study of the migration, speciation. and extinction ofspecies [1.2[. Biogeography has often been considered as a process that enforces equilibrium in the number of species in habitats. However. equilibrium in a system can also be considered as a minimum-energy configuration, so we see that biogeography can be viewed as an optimization process. This idea is further dis cussed in

13 [.

Biogeography-based optimization (BBO) is an evolutionary algorithm (EA) morjv.ned by the optimality perspective of nat ural biogeography, and was initially developed in [4[. Just as species migrate back and forth between islands, BBO operates by sharing information between individuals in a population of candidate solutions. BBO has shown good performance both on benchmark problems [

J-5[ and on real-world problems, includ

ing aircraft engine sensor selection [4 J, power system optimization [6,7J. groundwater detection [8 j, mechanical gear train design [9J, satellite image classification [10J. and neuro-fuzzy system training for biomedical applications

111 J.

Section 1.1 summarizes some of the important notation used in this paper. Section 1.2 gives an overview of BBO. Section 1.3 gives an overview and outline of the remainder of this paper. t)' This work was supponed by NSF erant 0816114 in the CMMI Division of the

Enginet�ring Directorate.

E-mail

d.j.simon@Csuohio.edu This section summarizes some of the notation used in BBO and in this paper. Some of these terms may be more general or more speCific in other contexts. The definitions indicated here are not universal. but are commonly used. and more importantly for our purposes, are specifically used in this paper. Biogeography-based optimization, an EA which is moti vated by the mathematical principles of natural biogeography.

A process whose state at time step (t -+-1)

depends only on the state at time t. The transition of the state from one time step to the next is deterministic. The sharing of a solution feature in BBO from one individual to another. The emigrating soluti on feature remains in the emigrating individual. This is similar to emigration ofa species in biogeography. in which representatives of a species leave an island but the species does not become extinct from the emigrating island.

A genetic algorithm with single-point crossover.

Agenetic algorithm with global uniform recombination. This

means that a solution feature ofan offspring can receive each solution feature from a different parent. The likelihood that any

given solution feature in the offspring comes from any given parent is proportional to that parent's fitness.

Acandidate solution in an EA.

Immigration: The replacement of an old solution feature in an individual with a new solution feature from another individual. The solution feature comes from the contributing individual by way of

emigration. The immigrating solution feature replaces a feature in the immigrating individual. �� : A process whose state at time step (� + 1) depends only on the state at time �. The transition of the state from one time step to the next is probabilistic. �� : The distribution of individuals in the search space. For example, if the search space consists of four possi ble solutions, �� 1 , � 2 , � 3 , � 4 � , and the population size is three, then a population distribution might consist of one copy of � 1 , zero copies of � 2 , two copies of � 3 , and one copy of � 4 . �� {�� : An independent variable of an optimization problem. For example, if the solution domain is a bit string, then a solution feature is a bit. �� : An EA in which recombination is performed to create an entire new population before any of the old population members are replaced. �� : An EA in which recombination is performed to create a single new individual which replaces one of the old individ uals in the population before the next recombination is performed. ≥�←�

��}��}��

This section gives an overview of BBO. BBO operates by migrating information between individuals, thus resulting in a modification of existing individuals. Individuals do not die at the end of a generation. In addition, a high-fitness BBO individual is unlikely to accept information from a low-fitness individual. This is motivated by biogeography and does not have an analog in GAs. In natural biogeography, a very habitable island is unlikely to accept immigrants from a less habitable island [12]. This is due to two reasons. First, the very habitable island is already saturated with species and does not have many additional resources to sup port immigrants. Second, the inhabitable island does not have very many species to begin with, and so it does not have many potential emigrants. BBO is motivated by biogeography but is not intended to be a simulation of biogeography. The analogy between biogeography and BBO breaks down at several points. For example, in biogeog raphy the number of species varies from island to island, while in BBO the number of solution features is constant for all individuals and is equal to the problem dimension. BBO can currently only deal with optimization problems of constant dimension; its extension to variable-sized problems is a topic for future research. Although the analogy is not perfect, the key point in BBO is that the migra tion of solution features between individuals is motivated by the mathematical theory of species migration in biogeography. Like other EAs, BBO operates probabilistically. The probability that an individual shares a feature with the rest of the popula tion is proportional to its fitness. The probability that an individual receives a feature from the rest of the population decreases with its fitness. When a copy of feature � from individual � | replaces a feature in individual � � , we say that � has emigrated from � | and immigrated to � � ; that is, � � ( � ) � | ( � ).

Although

nonlinear migration curves may give better optimiza tion results [5], in this paper we use linear curves as shown in Fig. 1. Fig. 1 depicts two BBO individuals. � 1 depicts a poor solution and � 2 depicts a good solution. The immigration probability for � 1 will thus be higher than that of � 2 , and the emigration probability for � 1 will be lower than that of � 2 . Note that if a good solution is obtained in the population, then there may be a high probability that the pop ulation will converge towards that solution, resulting in premature convergence. As with any other EA, an appropriate mutation rate needs to be used in BBO to balance exploration and exploitation. There are several ways to implement BBO. The original BBO algorithm, which we use in this paper, is called partial immigration- based BBO [13]. In this approach, for each feature in each individual 1 immigrati on ? emigration µ probability S 1 S 2 fitn ess ��}� ≥� Illustration of two BBO individuals using linear migration curves. �1 repre sents a poor solution and � 2 represents a good solution. we probabilistically decide whether or not to immigrate. If immi gration is decided upon, then a fitness-based probabilistic method (e.g., roulette wheel selection) is used to select the emigrating indi vidual. This gives the algorithm shown in Fig. 2 as a description of one BBO generation. We perform migration and mutation for each individual in the current generation before any individuals are replaced, resulting in a generational EA [14]. The migration decision requires that the individuals be sorted in order of fitness, which is a computational consideration. However, in almost all real-world EA applications, fitness function evaluation comprises the vast major ity of computational effort. ≥��

��

In previous work we derived a Markov chain model for BBO [15,16] . A Markov chain is a random process which has � possible state values [17, chap. 11]. The probability that the system transi tions from state � to state | is given by the probability � �| . The � × � matrix � =[� �| ] is called the transition matrix. Each state in the BBO

Markov

model represents a population distribution, that is, a dis tribution of individuals in the search space. Probability � �| is the probability that the population transitions from the �th population distribution to the |th population distribution in one generation.

Although

we use BBO Markov theory in this paper to derive a dynamic system model, the states in the dynamic system model are not the same as the states in the Markov model. BBO Markov states represent population distributions. BBO dynamic system states represent the proportion of each individual in the popula tion; that is, the �th state is the proportion of the �th individual in the population. The state dimension of the BBO dynamic system will thus be only a small fraction of the state dimension of the BBO

Markov

model. This makes the dynamic system model applicable to larger problems than the Markov model.

Section

2 reviews the BBO Markov model which forms the basis for this work and which was derived in [15,16]. Section 3 and fol lowing comprise the new contributions of this paper. Section 3 derives the BBO dynamic system model and some of its proper ties. We also extend the dynamic system model to a GA with global uniform recombination (GAGUR). Section 4 compares the dynamic system models of BBO, GAGUR, and GA with single-point crossover (GASP). We provide concluding remarks and suggestions for future work in Section 5.

Fig.

2. �� }�� { �� }�� z �� { �� z

k ��

�� k�� z

k � s � �� s�� {�� { z k � 2. A Markov model for BBO ��

�≥��≥�� {��

��

�� {�� {��

�{ �

��

}��

��}�� }��

��

�� {�� { ��

y ��

��}� ←� �� }�� {�� {� �� { x

i �� x i � s �� J i � s� �� {

�� j �� x

j � s �= x i � s �� J i � s� / {j � x j � s� / x i � s�}, i ? �≥,n�. �� |J i �

s�| / n/← {�� i �� s� �� ←� ��

��

�� }��} �� z

j � �� }� ←� j ��}��

�� k� �� {

∞ ∩∩∩∩∩∩∩� ∩ ∩ ∩ ∩ ∩ ∩ ∩ � x ≥ {�� k / ≥,..., v ≥ x ← {�� k / v ≥ � ≥,..., v ≥ � v ← x � {�� k / v ≥ � v ← � ≥,..., v ≥ � v ← � v �

� ��} �� y

k /

� � �� {{��} �� { ��

��

�� {��

��

�� }�� {

n ≥ ← x n {�� k / v i � ≥,...,N ��

��

i/≥ ��

�� ≥�� }��

��

�� {��

�� }�� { �� y

k / x m � k� {�� k / ≥,...,N ��

��

�� { �� }�

r ← x i ��

�� q �� { �� m�k� / �� r �� v

i � k. �� {�� n =← q �

��

i/≥ ��

N� �� n�� v ��

�� { �� x i ��

�� t �� }��

{�� y k � s � t ��

�� { �� s�� { ��

k ��

�� }�� t� ��

n ← ��

�� ≥��≥�� y

k � s � t +≥ = x i � s � �� v i / N. �≥� �� i/≥ ← ��

k�� y

k � �� y k v j j ��

�� }�� j ? J

i � s� �� y k � s� t�≥ / x i � s�� / �≥ m � k� � 1 � x m � k� � s� / x i � s�� m � k� �� { �� y k �� n ← →? �{ �� x i ��

��

v j j �� j/≥ �� / {y ≥ , . . . , y N } �� / { x ≥ ,x ≥ ,...,x ≥ ,x ← ,x ← ,...,x ← , . . . x n , x n , . . . , x n } .

�←� �� 1�·� �� {�� 1�A� / ≥ �{ A ��

≥≤?≥≤→?≥≤→ v ≥ �� v ← �� vn ��

�� q �� y

k �

��{�� { ��

�� v

�� t�� }��

��

��}�� { x

i �� i �

�� }�� y

k � t +≥ = x i �� P ki �v� �� }�� { x i �� i � �� s��

P ki �v� = ��y k,t+≥ = x i �

�� ≥≥� �� }��

m � k≥� m�k� v j j �� y k ≥ = x i � = ��y k ← = x i � �{ �k ≥ ,k ← � v i + ≥, v i . i=≥ i=≥ .= q s=≥ j J i � s� �≥ m � k� � ≥ � x m � k� � s� = x i � s�� + m � k� �≥←� n v j j ��{��

�≥��

j=≥ �� . v j j �≥ k � ≥ � x k � s� = x i � s�� + k P ki

�v� �� {�� k �≥� N� �� i �≥� n� ��

q s=≥ n ≥ j J i � s� n �� M h = x i � = �≥��

{�� N × n �� P�v�� }��

v k N �{

N �� }�� { n �� k=≥

�� w i ��

�� { ��

v j j j=≥ x i ��

�� {�� N ��}�� {��

� }��

}�� w = � w

≥ · · · w n � T �

�� Now �� p ��

��

�� w �� t + ≥�

�≥��p = .�� }�� }��

�� N t�� }�� {�� }�� p

i �� { x i ��

�� {�� ≥��≥��≥�� i �≥� n�� { p �� ≥� �� ≥��

�� N n �� w|v� = P J ki �v� ki J Y�w� Y �w� =J �

N×n

� J ki { � , ≥}, J ki = ≥ {�� k, J ki = w i {�� i k=≥ i=≥ �� v j jnN �≥ k � ≥ � x k � s� = x i � s�� + k n q s=≥ j J i � s� n . �� M h = x i � = p k i=≥ k=≥ ��

�� } �� {��

k=≥ v j j j=≥ ��

v �� w ��

q ��

�� T × T �� T �� { ��

n p k � p T � q T �≥ k � ≥ � x k � s� = x i � s�� + k v j j ��

�� T �� { �� n × ≥

��}�� T i = N �� T i

N� �� ←�� k=≥

p= . s=≥j J i � s� ��

T �� } �� {�� {��

�≥��

�� }�� { ��

��

�� t�� }�� {� �� { �� }�� n + N ≥T =. ��N

�� { ��} x i ��

�� t + ≥� �� }��

�←≥� ��

←� �� {� �� { �� {�� } T �� ≥�� { x

i ��

��

� t + ≥� �� }�� q ��

� �� {��

n p k � t� p T � t��≥ k � ≥ � x k � s� = x i � s��p i � t

+ ≥� =�� { �� ← �� p

T � t�� q �

�� {�� }�� P

ki �v�� s=≥k=≥ ��

�� k�� }�� y

k = x i �� t

+ ≥� �� }�� } ��

�� +

k v j � t� j ��

�� t�� }��

�≥��

{�� }�� }� �� }�� { ��}� ←�

��

�� }� �� }�� N �� N ��

��

�� { �� }

��}� �� y k {��

��}��

��

�� {�� }�� { �� N ��

��}� ��

�� {�� }� �� }��

�� y k ��

� ≥�N �� { ��} �� {�� }��

��

�� N � �� }�� { ��}� ←� ��

��

��}�� }�� }��

�� }� ��

�� }�� h�� }��

M h �� x i �� N ≥��M h = x i � = ��y k = x i � . �≥��N k=≥ �� y k ≥ = x i � = ��y k ← = x i � �{ y k ≥ = y k ← . �≥≥� j J i � s� ��

�� p �� {�� { t�

��} ��

�� {�� i �≥� n� }��

�� {��

�� { ��

p � t + ≥� = f �p�t��. �≥��

�� { �� n × n ��

�� U� �� U ij ��

�� x

j �� x i � �{

�� { �� {x} ��

��

�� u �{ ��

U ij = u d ij �≥ u� q d ij �≥�� d ij ��

�� } �� x

i �� x j �←←� �� ≥��. �� }��

��

p � t + ≥� = Uf �p�t��. �≥�� {

�� }�� U ��

��

�≥�� ≥��

Fig.

�3.�One�generation�of�the�BBO�algorithm�with�random�selection�of�the�immigrating�individual.�

3.1. �Special�case:��=0�written�as� It �is�instructive�to�consider�the�dynamic�system�when� k � = �0�for�Pr(yk,t�1 / x i | s)/Pr[y k,t � ( r �:�r�/�s)/x i ( r �:�r�/�s)]Pr(y k,t�1 ( s)/x i ( s)).� all

�k.�In�this�case,�there�is�no�possibility�of�immigration�and�(15)�(23)reduces�to�

The � first

�term�on�the�right�side�of�(23)�is�the�proportion�of�the�popu

q p i ( t ��1)�/�p k ( t)�1[x k ( s)�/�x i (

s)]�.�(20)�lation�which�has�all�bits�r�such�that�r�/�s,�equal�to�the�corresponding�

s/1� bits �in�x i . �We�denote�the�indices�of�these�individuals�as�L i ( s): k/1� Since �each�x i � is �distinct,�we�see�that�L i ( s)�/ {j�:�x j ( r �:�r�/�s)�/�x i ( r �:�r�/�s)}, i�?�[1,n].�(24)� q � � n � Note �that�|L i (

s)| /�2�for�all�(i,�s).�Now�we�can�write�(23)�as�1[x

k ( s)�/�x i ( s)]�/�1[k�/�i]�(21)� � s/1� � v j � j �?�L i ( s)� n � �! ! ! !"� j �?�J i � ( s)� n � v j j !!!!"� which �gives� n � Pr( y k,t�1� / �x i | s)�/�.�(25)� p i ( t ��1)�/�p k ( t)1[k�/�i]�/�p i ( t).�(22)� v j � v j ! j � j/1�j/1k/1� That

�is,�with�no�immigration�and�no�mutation,�the�proportionality�We�can�use�(1)�and�(14)�to�write�the�above�equation�as�

vector

�does�not�change�from�one�generation�to�the�next,�which�

agrees � with �intuition.�p j ! j � j �?�J i � ( s) Pr( y k,t�1� / �x i | s)�/�p j � . �(26) n 3.2. �Special�case:��=�1�and�random�feature�selection� j �?�L i � ( s)� p j j � If � k � =

�1�for�all�k,�then�the�BBO�algorithm�of�Fig.�3�becomes�a�

j/1� special

�type�of�a�genetic�algorithm�with�global�uniform�recombina

tion � (GAGUR)

�[23].�GAGUR�can�be�implemented�in�many�different�Fig.�4�shows�that�each�bit�s�?�[1,�q]�has�a�1/q�probability�of�being�

ways, � but

�if�it�is�implemented�with�the�entire�population�as�poten-selected�as�the�migrating�feature.�Therefore,�

tial � contributors �to�the�next�generation�[24],�and�with�fitness-based� � selection

�for�each�solution�feature�in�each�offspring,�then�it�is�equiv-

1alent�to�BBO�with�

k � = �1�for�all�k.�In�this�case,�immigration�takes�Pr(y k,t�1� / �x i ) �/�p j j � . �(27) p j � qp T �

place�for�all�individuals�in�the�population,�and�the�new�individual�

s/1�j�?�L i ( s)�j�?�J i � ( s)� that

�results�from�each�immigration�can�be�thought�of�as�an�offspring�

of � the

�previous�generation.�Suppose�also�that�in�addition�to�

k � = �1�This�is�a�quadratic�function�of�the�p i � terms �and�can�thus�be�written� for

�all�k,�each�immigration�trial�migrates�one�randomly�selected�bit.�as�

Then � the

�BBO�algorithm�of�Fig.�3�becomes�the�GAGUR�algorithm�of�

n n Fig. �4.�Pr(y k,t�1� / �x i ) �/�Y i,ab p a p b . �(28)The�probability�that�y k � at �the�(t�+�1)�st�generation�is�equal�to� x i ,

�given�that�solution�feature�s�was�selected�for�migration,�can�be�

a / 1 �b/1�

Fig.

�4.�One�generation�of�GAGUR�with�random�selection�of�the�immigrating�individual�and�random�selection�of�the�migrating�solution�feature.�

Eq. �(27)�shows�that�the�p 2 � coefficient �on�the�right�side�of�(28),�where� m � m �?�[1,�n],�can�be�written�as� qq� Y i,mm � / � m 1 [ m �?�� i ( s)]1[m�?�� i ( s)]/� m 1 [ m �?�(� i ( s)�� i ( s))].� s/1�s/1� (29) � From �the�definition�of�� i ( s)�in�(24)�we�know�that�i�?�� i ( s).�We�also� know � that �there�is�only�one�other�element�in�� i ( s).�The�other�ele ment �in�� i ( s),�say�,�has�a�bit�string�such�that�x ( r )= �x i ( r ) �for�all� r � //s.�But�since��//i�we�know�that�x ( s ) �//x i ( s ), �which�means� that � /?�� i ( s).�Therefore� � i ( s)�� i ( s)�/ {i}�for�all�s.�(30)� Eq. �(29)�can�therefore�be�written�as� q � Y i,mm � / � m 1 [ m �/�i]�/�q m 1 [ m �/�i].�(31)� s/1� We �can�use�(27)�to�show�that�the�p m p k � coefficient �(k�//m)�on�the� right � side �of�(28)�can�be�written�as� q � Y i,mk � � �Y i,km � / � m � 1 [ m �?�� i ( s)]1[k�?�� i ( s)]� s/1� q � � � k � 1 [ k �?�� i ( s)]1[m�?�� i ( s)]�for�m�//k.�(32)� s/1� The

�GAGUR�dynamic�system�model�can�thus�be�written�as�the�fol

lowing � set �of�n�coupled�quadratic�equations:� p i ( t ��1)�/�p T � ( t)Y i p ( t), i�?�[1,n]�(33)� where �Y i , mk � is

�the�element�in�the�mth�row�and�kth�column�of�Y

i . �If� mutation �is�included�in�the�GAGUR�algorithm,�then� p ( t ��1)�/�U�diag(p T � ( t)Y i p ( t))�(34)� where �diag(p T ( t ) Y i p ( t )) �is�the�n�×�n�diagonal�matrix�consisting�of� p T ( t ) Y 1 p ( t ), �...,�p T ( t ) Y n p ( t ). � 4. �Dynamic�system�model�results�

Section

�4.1�verifies�the�dynamic�system�model�derived�in�the�

previous � section. �Section�4.2�compares�the�dynamic�system�models� of

�GA�with�single-point�crossover�(GASP),�GAGUR,�and�BBO.�4.1.�Verification�of�dynamic�system�models�

The

�dynamic�system�model�for�BBO�is�given�in�(16)-(19)�with�

k � proportional �to�fitness,�and� k � =1 �� k . �The�dynamic�system�model� for � GAGUR �is�given�in�(16)-(19)�with� k � = �1,�which�is�equivalent� to � (34) . �The�dynamic�system�model�for�GASP�with�roulette-wheel� selection

�was�originally�developed�in�[25].�It�is�summarized�in�[22,�

chap. � 6] �as� p T � ( t)diag()U T

C(i)U�diag()p(t)�p

i ( t ��1)�/�(35)� ( p T � ( t)) 2 � where

�diag()�is�the�n�×�n�diagonal�matrix�consisting�of�the�ele

ments � of

��(fitness),�and�U�is�the�mutation�matrix�given�in�(18).�

C ( i )

�is�an�n�×�n�matrix�such�that�the�element�in�its�mth�row�and�kth�

column �is�the�probability�that�x m � and �x k � cross �over�to�produce�x i . � To � verify �the�dynamic�system�models,�we�consider�a�simple� three-bit � problem

�(n�=�8)�with�a�per-bit�mutation�rate�u�=�0.2.�The�fit

ness � values, �which�are�equivalent�to�unnormalized�BBO�emigration� rates, � are �given�as�follows:� (000) �/�8, (001)�/�1,� (010) � / �1, (011)�/�1,�(36)(100)�/�1, (101)�/�1,� (110) � / �1, (111)�/�9.� This �is�a�relatively�difficult�optimization�problem�because�x 1 � = �000� has

�a�high�fitness,�and�every�time�we�add�a�1�bit�to�it�the�fitness�

decreases � dramatically, �but�the�individual�with�all�1's�has�the�high est � fitness.

�We�begin�with�an�initial�population�with�proportionality�

vector � p (0) �/�[0.80.1 0.1�0�0�0�0�0] T . �(37)� Figs.

�5-7�show�some�dynamic�system�model�results�and�simulation�

results � for

�EAs�with�a�population�size�of�1000.�The�plots�provide�

confirmation � for �the�dynamic�system�models�presented�earlier.� The

�simulation�results�oscillate�around�their�mean�value,�which�is�

expected � because �of�the�mutation�operator.�The�simulation�results� will � vary

�from�one�simulation�to�the�next,�and�will�never�exactly�

match � the

�theory,�due�to�the�stochastic�nature�of�the�simulations.�

That

�is�why�the�dynamic�system�models�can�be�more�useful�than�

simulation; � the �models�are�exact�while�simulation�results�are�only� approximate. � 0 5 10 4 �2 10 simulation simulation mean theory

0 20 40 60 80 100

�6 10 �2 �1�3 BBO

GA/sp

GA/gur

percent of optimum percent of optimum 3 2 1 �4 10 0 1010
probability of mutationgeneration 10 ��}� �� BBO dynamic system results giving confirmation that simulation matches theory. The traces show the proportion of the optimal individuals for a typical simulation, the mean of that proportion over all generations, and the proportion according to the dynamic system model. 3 2.5 ��}� �� Dynamic system model results for a 3-bit problem (search space cardinality n = 8) showing the steady-state proportion of optimal individuals. 4.2. Comparison of dynamic system models Next we compare dynamic system model results between BBO,

GAGUR,

and GASP. We consider a problem whose fitness values are given as 8 for x i = (0···0) simulation simulation mean theory ? i = 9 for x i = (1···1) (38) 2 1 for all other x i . This is the same as (36) except that it is generalized for an arbitrary 1.5 number of bits. The proportionality vector of the initial population is given as 1 percent of optimum p (0) = 1 [1 ... 1 0] T . (39) n - 1 0.5 That is, the initial population is evenly distributed among the sub< optimal individuals, and there are no optimal individuals. Figs. 8-10 show steady-state dynamic system model results for three differ<

00 20 40 60 80 100

generation ��}� �� GAGUR dynamic system results giving confirmation that simulation matches theory. The traces show the proportion of the optimal individuals for a typical simulation, the mean of that proportion over all generations, and the proportion according to the dynamic system model. 6 5 simulation simulation mean theory percent of optimum 4 3 2 1 ent search space cardinalities, plotted as functions of mutation rate. Fig. 8 shows that BBO is much better at achieving a high percentage of optimal individuals than GASP and GAGUR for small problems. Figs. 9 and 10 show that as the problem dimension gets larger, BBO performance gets worse relative to the GAs for large mutation rates.

However,

BBO remains many orders of magnitude better than the GAs for small mutation rates, which are more typical for real-world problems. percent of optimum �5 10 �10 10 BBO

GA/sp

GA/gur

00 20 40 60 80 100

generation �3 �2 �1

101010

��}� �� GASP dynamic system results giving confirmation that simulation matches theory. The traces show the proportion of the optimal individuals for a typical probability of mutation simulation, the mean of that proportion over all generations, and the proportion according

to the dynamic system model. ��}� �� Dynamic system model results for a 5-bit problem (search space cardinality

n = 32) showing the steady-state proportion of optimal individuals.

�5 10 0 10 �2 10 BBO

GA/sp

GA/gur

BBO

GA/sp

GA/gur

12 1010 percent of optimum percent of optimum �10 10 �15 1010
�4 �3 �2 �1

10101010

6s probability of mutations problem dimension Fig.

�10.�Dynamic�system�model�results�for�a�7-bit�problem�(search�space�cardinality�

�=�128)�showing�the�steady-state�proportion�of�optimal�individuals.?�Fig.�13.�Dynamic�system�model�results�for�mutation�rate�=�10%�per�bit�showing�the�

steady-state �proportion�of�optimal�individuals.� �5 10 percent of optimum �10 10 �15 10 �20 10 BBO

GA/sp

GA/gur

12 1010 problem dimension Fig.

�11.�Dynamic�system�model�results�for�mutation�rate�=�0.1%�per�bit�showing�the�

mutation

�rate�is�low,�as�is�typical�of�real-world�problems.�

Figs. � 12

�and�13�show�that�as�the�mutation�rate�increases,�BBO�

remains � better �than�the�GAs�for�small�problem�dimensions,�but� becomes � worse �than�GASP�as�the�problem�dimension�increases.� As � seen

�in�Fig.�11,�with�realistic�mutation�rates�BBO�is�much�

better � than �the�GAs�for�all�problem�dimensions.�Furthermore,�the� relative � advantage �of�BBO�increases�as�the�problem�dimension� increases. � This �is�consistent�with�the�conclusions�presented�in�[23]� which � were

�based�on�a�different�type�of�analysis�and�which�were�

confirmed � with �a�variety�of�standard�benchmark�simulations.� Next � we �compare�the�dynamic�system�model�results�of�BBO,� GASP, � and �GAGUR,�on�standard�benchmark�functions.�The�Nee dle �

Function

�is�given�in�(38).�The�Onemax�Function�has�a�fitness�

that � is

�proportional�to�the�number�of�one-bits�in�each�bit�string.�

The

�Deceptive�Function�is�the�same�as�the�Onemax�Function,�

except � that

�the�bit�string�with�all�zeros�has�the�highest�fitness.�

The � continuous

�functions�that�we�use�are�listed�in�Table�1�and�

steady-state �proportion�of�optimal�individuals.� Figs.

�11-13�depict�the�same�information�as�that�shown�in�

Figs. � 8-10 ,

�but�presented�in�a�different�way.�Figs.�11-13�show�

dynamic

�system�model�results�for�three�different�mutation�rates,�

plotted � as

�functions�of�problem�dimension.�Fig.�11�shows�that�BBO�

is � much

�better�than�the�GAs�for�all�problem�dimensions�if�the�are�

documented �in�[26-28].�We�implemented�the�continuous�func tions � as �two-dimensional�functions�whose�independent�variables� are � coded

�with�three�or�four�bits�per�independent�variable.�This�

gives � an

�optimization�problem�with�either�six�or�eight�bits�total,�

which

�results�in�a�search�space�cardinality�of�either�64�or�256.�We�

initialized � the �population�with�a�uniform�distribution�over�all�of� the � non-optimal �solutions.�The�initial�population�did�not�have�any� optima. � We �recorded�the�percent�of�optimal�solutions�in�the�pop ulation � after

�10�generations,�which�gives�an�idea�of�how�fast�each�

algorithm � converges. �Table�1�shows�the�results.�Note�that�these�are� BBO

GA/sp

GA/gur

12 1010 �5 10 percent of optimum �10 10 problem dimension Fig.

�12.�Dynamic�system�model�results�for�mutation�rate�=�1%�per�bit�showing�the�

not

�simulation�results,�but�exact�dynamic�system�model�results.�

For

�both�the�64-bit�and�256-bit�problems,�BBO�performed�the�

best � in

�15�out�of�19�benchmarks.�More�importantly,�for�very�difficult�

problems � (the �Needle�and�Deceptive�Functions),�BBO�performed� better � than �GASP�and�GAGUR�by�orders�of�magnitude.� These �results�are�not�intended�to�give�a�comprehensive�com parison � of �BBO�and�GAs;�extensive�comparisons�between�BBO�and� other � EAs �using�standard�benchmark�functions�are�shown�in�[3].� The � theory

�and�results�here�are�instead�intended�to�show�how�

dynamic

�system�models�can�be�used�to�compare�EAs�in�situations�

where � probabilities �are�extremely�small�and�where�Monte�Carlo� simulations �are�therefore�not�useful.�Dynamic�system�models�can� also � be

�used�to�study�the�effect�of�various�parameter�settings�and�

learning � approaches. �Dynamic�system�models�can�also�aid�in�the� development � of �adaptive�algorithms�or�parameter�update�schemes� that � work

�well�on�many�different�types�of�problems.�Our�dynamic�

system � models �can�also�be�used�to�help�understand�the�behav steady-state

�proportion�of�optimal�individuals.?�ior�of�BBO;�for�example,�how�and�why�it�works�well,�or�does�not�

Table 1

Dynamic

system results on benchmark functions. The number in each cell indicates the percentage of optimal individuals in the population after 10 generations. The best

result for each benchmark/cardinality combination is shown in boldface font.

FunctionCardinality=64Cardinality=256

BBOGAGURGASPBBOGAGURGASP

Needle6.97×10

-3

2.32×10

- 10

2.17×10

- 6

6.72×10

-3

9.95×10

- 6

6.48×10

- 6

Onemax46.0447.6742.6422.4423.8419.43

Deceptive3.89×10

-3

2.25×10

- 4

2.33×10

- 4

1.03×10

-3

5.36×10

- 5

5.13×10

- 5

Rosenbrock10.373.569.136.604.186.49

Ackley58.9225.4071.3843.4054.1770.00

Fletcher74.3088.4128.8832.1923.1523.73

Griewank67.8244.1849.0036.1215.0725.61

Penalty #129.6924.9827.7726.2225.0225.68

Penalty #232.8324.9628.9813.0312.5114.08

Quartic39.0926.1334.1218.6412.4917.01

Rastrigin43.9350.0541.7946.8514.6442.43

Schwefel 1.269.3725.2949.2135.9114.0225.07

Schwefel 2.2269.1425.8051.2738.1013.3626.84

Schwefel 2.2175.6566.8462.8949.0339.8238.60

Schwefel 2.2615.930.471.3038.0715.698.70

Sphere69.6347.6949.2135.9512.5024.94

Ellipsoid65.8256.0748.8434.1516.0824.80

Michalewicz34.0133.3030.3814.4712.3215.67

Step50.0425.0437.5625.5112.5219.45

workwell,oncertaintypeofproblems.Thispaperdoesnotexplore these many possible research directions, but we envision that the groundwork laid here will encourage these ideas and make their pursuit possible.

5. Conclusion

Mature EAs, such as GAs, have a well-structured theory. This paper attempts to extend BBO theory in that direction to enable its use and study as an alternative EA.Wehave summarized a pre- viously derived BBO Markov model and used it to obtain a new dynamic system model for BBO.Wehave further shown how it can be used to derive a new dynamic system model for GAGUR. We compared the dynamic system models between BBO, GAGUR, and GASP on some simple optimization problems.Wehave seen that BBO far outperforms GAs when mutation rates are low (0.1% per bit), as are typically used for real-world problems. In addition, the relative advantage of BBO increases as the problem dimension increases. This indicates that BBO can be especially useful for large, real-world problems when small mutation rates are used. For some real-world problems where small population sizes are required due to huge computational complexity for fitness evalua- tion, itmaybe desirable to use large mutation rates on the order of 10% per bit[29]. In this case BBO still outperforms the GAs for small problem dimensions,butGASPisthebestperformerforlargeprob- lems. Notethattheseconclusionsaresimilartothoseof[23],which were obtained using a different approach. Reference[23]also pro- vides amoreextensivediscussionoftheconceptualsimilaritiesand differences between GAs and BBO. There are many interesting possibilities for future work. One is to extend BBO using features of natural biogeography theory[1,2]. This could include modeling nonlinear migration curves, modeling species populationsandtheireffectsonmigration,modelingpreda- tor/prey relationships,includingspeciesmobilitiesinthemigration model, including directional migration momentum as a temporal effect from one generation to the next, modeling habitat area and isolation, and many others. In this paper we used Markov theory for partial immigration- based BBO to derive a dynamic system model. In addition,we analyzed agenerationalBBOalgorithm;thatis,modificationofeach individual in the current generation occurs before any individuals are replaced in the population[14]. Future work could include the extension

of our Markov and dynamic system models for othervariations of BBO. These variations include partial emigration-

based BBO,singleimmigration-basedBBO,singleemigration-based BBO [13] , oppositional BBO[30], and a steady-state BBO in which individuals in the population are modified with replacement. It would also be of interest to extend the Markov theory and dynamic system modeltoBBOwithnonlinearmigrationcurves[5].Also,our results have been restricted to problems with binary representa- tions, anditwouldbeinterestingandusefultodevelopMarkovand dynamicsystemmodelsofBBOwithothertypesofrepresentations.

Finally,

our results are exact only in the limit as the population size approaches infinity. Many EA applications have large populations, but many others do not. Further work could focus on obtaining a dynamic system model for small population sizes, perhaps by combining states into "meta-states," or perhaps by using the BBO

Markov

model in either[13]or[15]. These extensions would allow analytical comparisons between different types of BBO algorithms rather than a reliance on sim- ulation results. Although simulation results are important and necessary, if used apart from theory they can be misleading. For example, Fig. 11shows that BBO is orders of magnitude better than GAs for large problems with a low mutation rate. However, since the probabilities inFig. 11are so small, it would be difficult to derive such a conclusion from simulation results because of the huge amount of computation that would be required.

Another

suggestionforfutureworkistocombineBBOwithother EAs. Hybrid EAs are an important topic of research and can exploit the strengths of multiple methods in a single optimization algo- rithm [31] . BBO has already been combined with opposition-based learning [30] . Future work could focus on combining BBO with the many other EAs that are available. These hybrid algorithms should be studied not only with benchmarks and real-world optimization problems, but also with analytical approaches such as the Markov and dynamicsystemtheoryusedinthispaper.Suchanalyticaltools include the stochastic character of EAs, but do not depend on the random results of simulation studies to draw general conclusions.

References

[1]M.Lomolino, B. Riddle, J. Brown, Biogeography, Sinauer Associates, 2009. [2] R. Whittaker, Island Biogeography, Oxford University Press, 1998. [3] H.Ma,An analysis of the equilibrium of migration models for biogeography- based optimization, Information Sciences 180 (2010) 3444-3464. [4] D.Simon,Biogeography-basedoptimization,IEEETransactionsonEvolutionary

Computation 12 (December) (2008) 702-713.

[5] H.Ma,S. Ni,M.Sun,

Equilibrium species counts and migration model trade- offs for biogeography-based optimization, in: IEEE Conference on Decision and

Control, Shanghai, December 2009, pp. 3306-3310.

[6] R. Rarick, D. Simon, F. Villaseca, B. Vyakaranam, Biogeography-based opti- mization and the solution of the power flow problem, in: IEEE Conference on Systems, Man, and Cybernetics, October 2009, pp. 1029-1034. [7] P. Roy, S. Ghoshal, S. Thakur, Biogeography-based optimization for economic load dispatch problems, Electric Power Components and Systems 38 (January) (2010) 166-181. [8] H. Kundra, A. Kaur, V. Panchal, An integrated approach to biogeography based optimization with case based reasoning for retrieving groundwater possibility, in: 8th Annual Asian Conference and Exhibition on Geospatial Information,

Technology and Applications, August 2009.

[9] V. Savsani, R. Rao, D. Vakharia, Discrete optimisation of a gear train using biogeography based optimisation technique, International Journal of Design

Engineering 2 (2009) 205-223.

[10] V.Panchal,P.Singh,N.Kaur,H.Kundra,Biogeographybasedsatelliteimageclas- sification, International Journal of Computer Science and Information Security

6 (January) (2009) 269-274.

[11] M. Ovreiu, D. Simon, Biogeography-based optimization of neuro-fuzzy sys- tem parameters for diagnosis of cardiac disease, in: Genetic and Evolutionary

Computation Conference, July 2010, pp. 1235-1242.

[12] R. MacArthur, E. Wilson, The Theory of Biogeography, Princeton University

Press, 1967.

[13] D. Simon, A probabilistic analysis of a simplified biogeography-based optimization algorithm, Evolutionary Computation, in print, available at http://embeddedlab.csuohio.edu/BBO. [14] F. Vavak, T. Fogarty, Comparison of steady state and generational genetic algorithms for use in nonstationary environments, in: IEEE International Con- ference on Evolutionary Computation,May1996, pp. 192-195. [15] D. Simon,M.Ergezer, D. Du, R. Rarick, Markov models for biogeography-based optimization, IEEE Transactions on Systems, Man, and Cybernetics - Part B:

Cybernetics 41 (January) (2011) 299-306.

[16] D. Simon, M. Ergezer, D. Du, Population distributions in biogeography-based optimization algorithms with elitism, in: IEEE Conference on Systems, Man,

and Cybernetics, October 2009, pp. 1017-1022.[17] C. Grinstead, J. Snell, Introduction to Probability, American Mathematical Soci-

ety, 1997. [18] S. Venkatraman, G. Yen, A simple elitist genetic algorithm for constrained optimization, in: IEEE Congress on Evolutionary Computation, June 2004, pp.

[PDF] A Dynamic System Model of Biogeography-Based Optimization

D58 *3,&,*)8(-41&78-.5(8:4-.4*): *3*(*%+&(5:'

3)9-*1*

422438H

TICE: this is the author's version of a work tha

425:9.3,-&3,*87*8:19.3,+7429-*5:'1.8-.3,574(*888:(-&85**77*;.*<*).9.3,(477*(9.4388

97:(9:7&1+472&D.3,&3)49-*76:&1.9=(4397412*(-&3.8282&=349'*7*B*(9*).39-.8)4(:2*39

879.(1*.8'74:,-994=4:+47+7**&3)45*3&((*8

8'=9-*1*(97.(&13,.3**7.3,425:9*7"(.*3(**5&792*39&93,&,*)"(-41&78-.5"$9-

3,&,*)"(-4

1&78-.5"$47247*.3+472&9.4351*&8*(439&(91

Dan Simon

University. and Computer United

1. Introduction

13 [.

J-5[ and on real-world problems, includ

111 J.

Enginet�ring Directorate.

E-mail

A process whose state at time step (t -+-1)

A genetic algorithm with single-point crossover.

Acandidate solution in an EA.

Although

Markov

Although

Markov

Section

N×n

1alent�to�BBO�with�

Section

C(i)U�diag()p(t)�p

0 20 40 60 80 100

GA/sp

GA/gur

GAGUR,

00 20 40 60 80 100

However,

GA/sp

GA/gur

00 20 40 60 80 100

101010

GA/sp

GA/gur

GA/sp

GA/gur

10101010

GA/sp

GA/gur

Function

GA/sp

GA/gur

Table 1

Dynamic

FunctionCardinality=64Cardinality=256

BBOGAGURGASPBBOGAGURGASP

Needle6.97×10

2.32×10

2.17×10

6.72×10

9.95×10

6.48×10

Onemax46.0447.6742.6422.4423.8419.43

Deceptive3.89×10

2.25×10

2.33×10

1.03×10

5.36×10

5.13×10

Rosenbrock10.373.569.136.604.186.49

Ackley58.9225.4071.3843.4054.1770.00

Fletcher74.3088.4128.8832.1923.1523.73

Griewank67.8244.1849.0036.1215.0725.61

Penalty #129.6924.9827.7726.2225.0225.68

Penalty #232.8324.9628.9813.0312.5114.08

Quartic39.0926.1334.1218.6412.4917.01

Rastrigin43.9350.0541.7946.8514.6442.43

Schwefel 1.269.3725.2949.2135.9114.0225.07

Schwefel 2.2269.1425.8051.2738.1013.3626.84

Schwefel 2.2175.6566.8462.8949.0339.8238.60

Schwefel 2.2615.930.471.3038.0715.698.70

D58 3,&,)8(-41&78-.5(8:4-.4): 3(%+&(5:'

3)9-1

425:9.3,-&3,878:19.3,+7429-5:'1.8-.3,574(888:(-&85**77;.<).9.3,(477(9.4388

97:(9:7&1+472&D.3,&3)49-76:&1.9=(4397412(-&3.8282&=349'7B*(9).39-.8)4(:239

879.(1*.8'74:,-994=4:+47+7**&3)453&((8

8'=9-1(97.(&13,.3**7.3,425:97"(.3(5&79239&93,&,)"(-41&78-.5"$9-

1&78-.5"$47247.3+472&9.4351&8*(439&(91

00 20 40 60 80 100