J. Cent. South Univ. (2012) 19: 2247-2265

DOI: 10.1007/s11771-012-1269-x

Global optimization by small-world optimization algorithm based on social relationship network

LI Jin-hang(李晋航)¹, SHAO Xin-yu(邵新宇)¹, LONG Yuan-ming(龙渊铭)¹,

ZHU Hai-ping(朱海平)¹, B. R. Schlessman²

1. School of Mechanical Science and Engineering, Huazhong University of Science and Technology,Wuhan 430074, China;

2. Air Force Research Laboratory, Wright Patterson Air Force Base, Dayton 45433, U.S.A

? Central South University Press and Springer-Verlag Berlin Heidelberg 2012

Abstract: A fast global convergence algorithm, small-world optimization (SWO), was designed to solve the global optimization problems, which was inspired from small-world theory and six degrees of separation principle in sociology. Firstly, the solution space was organized into a small-world network model based on social relationship network. Secondly, a simple search strategy was adopted to navigate into this network in order to realize the optimization. In SWO, the two operators for searching the short-range contacts and long-range contacts in small-world network were corresponding to the exploitation and exploration, which have been revealed as the common features in many intelligent algorithms. The proposed algorithm was validated via popular benchmark functions and engineering problems. And also the impacts of parameters were studied. The simulation results indicate that because of the small-world theory, it is suitable for heuristic methods to search targets efficiently in this constructed small-world network model. It is not easy for each test mail to fall into a local trap by shifting into two mapping spaces in order to accelerate the convergence speed. Compared with some classical algorithms, SWO is inherited with optimal features and outstanding in convergence speed. Thus, the algorithm can be considered as a good alternative to solve global optimization problems.

Key words: global optimization; intelligent algorithm; small-world optimization; decentralized search

1 Introduction

Global optimization is one of the most important research fields in operation research. The ordinary requirement is to find optimal targets that are interpreted with cost function under constrictions. The traditional optimizations, such as generalized simplex method and iterative gradient method, face several obstacles like single point calculation, which is easy to fall into local trap and effective only in few conditions.

With the increasing complexities of target functions, such as nonlinear and non-differentiable, intelligent algorithms have become a very active area of research. Researchers and engineers from system engineering, automation, computer science, management engineering, mining and mechanical engineering and so on, have adopted intelligent algorithms in solving sophisticated problems.

In intelligent algorithms, direct search approaches are the methods of choice. The best known of these are algorithms by predatory search (PS) [1], evolution strategies (ES) [2] and genetic algorithms (GA) [3]. The primary method is to generate plenty of vector variables, which stand for candidate solution. The algorithms decide whether the variables are adopted or abandoned. Most algorithms do that according to greedy criterion judging that whether the value of cost functions decreases. This way of search strategies converges rapidly but runs the risk of becoming trapped in a local minimum. Afterwards, parallel computing is adopted to forestall misconvergence. Through parallel computing of several vectors, the better solutions can help others jump out from local minimum. Differential evolution (DE) [4] is an example of improvement of genetic algorithm. On the other hand, there are other algorithms that are used to avoid misconvergence, such as simulated annealing (SA) [5] and tabu search (TS) [6]. Simulated annealing simulates the process of annealing of metal and guides searching process according to the transference probability of Boltzmann equation. Annealing relaxes the greedy criterion by occasionally permitting an uphill movement. Tabu search introduces memory scheme into searching process. Tabu area can prevent repetition from searching process. It can make the algorithm accept worse solution and jump out the trap. Furthermore, there are some interesting algorithms simulating behavior of animals, such as particle swarm optimization (PSO) [7] simulating birds and fish in predation, ant colony optimization (ACO) [8] simulating ants searching   food, and artificial bee colony algorithm (ABC) [9] simulating bees working together for honey. These algorithms work as predator of animals in nature and search their own best value. They can be called bionic algorithm. Recently, there is a hot spot from simulating relationship between social members, such as artificial life algorithm (AL) [10] simulating dependency of animals in food chain, and cultural algorithm (CA) [11] simulating the properties of different cultures of human society in identity, rejection, exchange and shift. The small-world optimization algorithm (SWO) proposed by us is still an efficient algorithm based on six degrees of separation theory in human sociology. The six degrees of separation theory reveal high degree of clustering and low and similar average length (as compared to random networks with the same N and <  k  >) in interpersonal network. That means, on the average, there is one short link between any two members. This character can help the SWO find appropriate target fast.

2 Background and related work

Small-world designation was first proposed by the Karinthy in 1929. He hypothesized that “any two individuals could be connected through at most five acquaintances” [12]. In 1967, the Milgram’s mail delivery experiment revealed the theory of small-world effect and proposed six degrees of separation principle [13]. Next, WATTS and STROGATZ brought much attention to the small-world phenomenon in theory and brought out a ring model for closing small-world network [14-15]. And then, KLEINBERG found that a simple strategy draw from a lattice grid can generate a small-world network and also found some interesting properties such as searchable in this model [16]. Moreover, WATTS et al made a great progress and proposed a small-world coming from human society communication network [17]. This model revealed more stable and rapid feature in quick search and was more close to the real network with small-world property like social community network, literature citation network, etc. It quickly became the hotspot of complex systems and complexity theory of research.

2.1 KLEINBERG model and its algorithm

KLEINBERG in his model found the cues needed for discovering short chains between two arbitrary nodes emerged in a very simple network model built from two-dimensional lattice. More details could be seen in Fig. 1 [16]. The network model is derived from a n×n lattice. Each node, u, has a short-range connection to its nearest neighbors (a, b, c and d ) and a long-range connection to a randomly chosen node, where node v is selected with probability proportional to [d(u, v)]^-α, where d(u, v) is the lattice distance between u and v, and α≥0 is a fixed clustering exponent. More generally, for p, q≥1, each node u has a short-range connection to all nodes within p lattice steps, and q long-range connections generated independently from a distribution with clustering exponent α. They are rich in structured short-range connections and have a few random long- range connections. Long-range connections controlled by a clustering exponent α, are added, which determines the probability of a connection between two nodes as a function of their lattice distance.

Fig. 1 Navigability of small-world networks in KLEINBERG model [16]

This model has a simple “geographic” interpretation: individuals live on grid and know their neighbors for some number of steps in all directions; they also have some number of acquaintances distributed more broadly across the grid. Viewing p and q as fixed constants, it obtains a one-parameter family of network models by tuning the value of the exponent α.

The algorithmic component of the model is based on MILGRAM’s experiment. The goal is to transmit a message from s to t in as few steps as possible. In particular, the message holder u in a given step has knowledge of lattice structure and the location of target.

Based on this model, KLEINBERG gives out three principles.

Principle 1: There is a constant α₀, depending on p and q but independent of n, so that when α=0, the expected delivery time of any decentralized algorithm is at least α₀n^2/3.

Principle 2: There is a decentralized algorithm Λ and a constant α₂, independent of n, so that when α=2 and p=q=1, the expected delivery time of Λ is at most α₂(logn)².

Principle 3: Let 0≤α<2. There is a constant α_r, depending on p, q and r, but independent of n, so that the expected delivery time of any decentralized algorithm is at least α_rn^(2-α)/3. Let α>2. There is a constant α_r, depending on p, q and r, but independent of n, so that the expected delivery time of any decentralized algorithm is at least α_rn^{(α-2)/(α-1)}.

Above all, in Kleinberg model, only when α=2 and p=q=1, the model gets fast searchable ability and its expected delivery time L_max~(logn)².

2.2 WATTS model and advantages in navigation

After KLEINBERG, WATTS et al [17] proposed a model for the small-world phenomenon based on a class of social relationship network. They presented a model for a social network that is based upon social structures and offers an explanation for the phenomenon of search ability. It explains the real social network structure as follows: The individual is familiar with each other as they are in a number of small groups according to some kinds of categories, such as occupations, geographic locations or interests. These groups can be categorized together into larger groups according to their common features. Like this, they are organized in a tree model in which the root stands for the whole society. Moreover, WATTS argued that individuals are usually clustered by more than one categories, which means that the social individual is familiar with each other not only in one kind of interest. For example, two strangers in the working relationship may be acquaintances in a school relation as they are classmates. Thus, the two men know each other within the whole social network. It was demonstrated by WATTS that multi-category of the community can reveal six degrees of separation theoretically and accelerate the decentralized search speed of network.

2.2.1 Category tree model

In one category (one solution space in our algorithm, and the space can be changed into another space by mapping function), the individual (candidate solution in our algorithm) is organized into one category tree model. Within the hierarchical level, it can define d_ij as the distance equal to their common branch level, as shown in Fig. 2(a). Individuals (dots) belong to groups (ellipses) which in turn belong to groups of groups and then give rise to a hierarchical categorization scheme. If vertexes i and j are in the same group, they are the short range contacts, and set d_ij=1. Otherwise, the higher the common branch level, the greater the distance between them.

But as depicted in WATTS’ theory, vertexes i and j in different groups may be acquaintances in probability, like those in the real social network. As such, the probability of acquaintance between individuals i and j decreases with decreasing the similarity of the groups to which they respectively belong. When the distance between them is longer, the probability they know each other will be smaller. The probability of two nodes connected in different groups meets  where α is a tunable parameter, and c is a normalizing constant. It chooses a second node j uniformly among all nodes that have distance d_ij from i. Repeat this process until a network has been constructed in which individuals have an average number of friends z. We can call the relationship between them as the long range contacts. α is the acquaintance parameter. If α grows up, two nodes only meet in short distance. On the contrary, if α grows down and near to zero, nodes have the same probability to connect with each other. This will generate a uniform random graph. Note that different α values affect the efficiency of decentralized search in this network model.

Fig. 2 Different distances with different common branches in hierarchical tree model [17]: (a) ; (b)

2.2.2 Two categories in social relationships

In WATTS’ theory, social networks have different categories for grouping. We use h as category index, h=1, 2, …, H. Each node in small-world has its own coordinate in H categories.  and  are denoted as the coordinate of node i and the distance of node i, and j in h category, respectively. Because the social distance stresses similarities rather than differences, it can get d_ij=

 h=1, 2, …, H, to denote the distance of node i

and node j in the multi-category tree model (or in their whole world). For instance, as shown in Fig. 2(b), individuals i and j can be close in dimension h=1, and individuals j and k can be close in dimension h=2, yet i and k can be far apart in both dimensions.

In conclusion, it has been demonstrated by WATTS that the hierarchical tree model, which could be fast searched by a decentralized searching strategy, always meeting α>0, H>1. When H=2, the efficiency of searching is the highest of all. While increasing the number of independent dimensions from H=1 yields a dramatic reduction in delivery time for values of α>0, this improvement is gradually lost as H increases further. For expected delivery length, WATTS adopted a more realistic, functional notion of efficient search, defining for a given message failure probability p≈0.25, a searchable network as any network for which q, the probability of an arbitrary message chain reaching its target, is at least a fixed value r=0.05. There is

q=á(1-p)^L?≥r                                 (1)

The maximum average transfer length áL? can be calculated as

áL?≤lnr/ln(1-p)≈10.4                          (2)

So, it is very important to note that there is no relation between the maximum average transfer steps in WATTS’ model and the network scale N.

2.3 Related work in small-world informed optimal algorithm

Some kinds of small-world networks, generated by a specific strategy, have been proven to have a fast decentralized searching ability as the model mentioned before. KLEINBERG firstly introduced small-world network into lattice research to solve the optimal problem via local search strategy. Then, WALSH [18] adopted the idea to solve the search problem in graph theory research. CHEN et al [19] pointed out that different values of the spread probability parameters will affect the quick searching feature of small-world. All the above-mentioned researchers made a great contribution to the theory of small-world structure with quick decentralized search.

Inspired by the small-world effect and its decentralized searching ability, scholars have made some useful attempts at algorithms in global optimization. A small-world topology structure was introduced in PSO by CUI et al [20] to simulate the true swarm behavior. The method has made PSO more stable than before. DU et al [21] adopted KLEINBERG lattice model, designed short and long search operator, and yielded one kind of small-world algorithm. This algorithm was called as K-SWO. LI et al [22] proposed decimal-coding small world optimization algorithm (DSWOA) based on KLEINBERG’s model and demonstrated its stability and fast convertible rate for high-dimensional optimization problems. WANG et al [23] adopted a chaotic map to design chaotic small-world optimization algorithm (CSWOA) to solve the constrained parameters in model predictive control. He drew a conclusion that it is suitable for real-time optimization of the process control. YANG and WANG [24] also referenced the KLEINBERG model and proposed a decentralized search strategy with faster convergence speed and achieved good search performance. Those scholars proposed or improved algorithms based on the quick search features of KLEINBERG’s lattice model. However, KLEINBERG model also has some weak points, compared to WATTS model. The comparison between the WATTS’ model and the KLEINBERG’s model is described as below.

KLEINBERG’s model uses geographical coordinate to judge distance in one categories but WATTS’ model adopts more than one categories such as interests and working relationship in social network. So, WATTS’ model is closer to the real society. To some extent, KLEINBERG’s model can be regarded as a special case of WATTS’ model [25].

The maximum average transfer step L_max in KLEINBERG’s lattice model is proportional to the network scale N. We get L_max~(logN)², only when α=2 and p=q=1. Parameter α denotes the power-law exponent of long range connect probability, p denotes the number of the short range contacts and q denotes the number of the long range contacts. However, there is no relation between the maximum average transfer steps in WATTS’ model and the network scale N. So, the computing complexity decided by L_max designed in WATTS’ model will not grow up with the size of network N increasing.

KLEINBERG’s study [26] showed that its model has the quick search property but only in specific conditions. It brought a lot of limitations and more precise parameter setting in case of saving search ability. And this defect blocked up the improvement of the algorithm in the further work. On the contrast, WATTS’ researches proved that most small-world networks built with its model more than one categories have a quick search property. So, the property donated from its model can guarantee the algorithm designed with the nature of fast search.

3 Small-world optimization

3.1 Framework

The basic idea of small-world optimization (SWO) algorithm’s can be described as simulating of Milgram’s mail delivery experiment. It delivers mails starting from a number of different locations to specific target where address is unknown in the search space. The holder of a mail, represented as node, acts as a candidate solution. Each node passes a mail to the next node after evaluating the cost function which is to determine whether the contact node is closer to the target point. Each mail will move to the target node to achieve the purpose of optimization step by step of the cooperation in the small world network.

Based on the WATTS’ theory, we can encode the search space by establishing a categories tree model to build a WATTS’ small-world network, which shortens the average distance between any two nodes and accelerates the searching speed. With the help of the network, a simple decentralized searching method can find the optimal target in few steps.

The SWO algorithm process can be listed as follows, and the flowchart is shown in Fig. 3.

Step 1: Establish the WATTS’ small-world network from search space. Each node in network has its own long and short range contacts.

Step 2: Set iteration counter c=0.

Step 3: Generate the initial cluster Q(t₀), where t₀ is the threshold in the process. Like other algorithms, SWO should encode the search space by binary code under the constraint of the optimizing problem. And then, SWO gets the initial nodes through a normal stochastic selection mechanism.

Step 4: Query and evaluate contacts. Each node in cluster draws out a number of contacts for query. All the contacts coming from the categories tree model contain long and short range contacts. Use a cost function to calculate their fitness which stands for the distance to the target.

Fig. 3 Flowchart of small-world optimization algorithm

Step 5: Deliver the mail. The current nodes in cluster choose their contacts which have better fitness than before and forward the mail to it. After that, those nodes quit from the cluster and add the close one in this mail holder cluster.

Step 6: Make a judgment whether SWO meets the termination condition or not. If the algorithm meets the termination condition, stop the whole process and output the result. Otherwise, continue to the next step.

Step 7: Set iteration counter c=c+1, and return to Step 4.

3.2 Encoding and initiation

Binary encoding method was the best choice to present the search space. Supposing n is code length, D is the dimension of X and m is the initial cluster size, for each node, the code should be presented as X={x₁, x₂, …, x_D}R^D, x_i={b_i1, b_i2, …, b_in}, i=1, 2, …, D.

The initial cluster is composed of the mail holders. Each node represents candidate solution to the actual problem. The choice of the cluster size m depends on the computing ability of the computer. The initial method is described as follows:

Stochastically generate ξ_iU(0, 1], and let

                              (3)

Generate m nodes iteratively to get an initial cluster. In some cases, the size m can be set as a dynamic variable. For example, some mails should be removed due to delivery failure judged by the decay rate of delivery, as well as, new mail can be added to make up the quantity for insufficient members.

3.3 Organizing candidate solutions into small-world network

WATTS’ categories tree model can reduce the average transfer length of the space and accelerate optimal searching speed to formulate the small world network. According to the structure of the tree model, referencing by IP address group strategy in internet, we encode the search space by binary code and use the mask code to group these nodes. In this way, we produce a category tree model. Using mask code we can easily get one node’s group ID and two node’s distance. We can also find a node in a specific distance.

Set a node code X={x₁, x₂, …, x_D}R^D, x_i={b_i, b_i, …, b_i}, i=1, 2, …, D, corresponding to mask code M={m₁, m₂, …, m_n}, in which b_ik, m_k{0, 1}, k=1, 2, …, n. Among node codes, the value of the number in mask code which is 1 represents the group ID code digit, and the value which is 0 represents the member ID code digit. Supposing that the length of group ID code is s, and n is the total length of the code, member code length g=n-s. So, the mask code can be described as M=  …,    …,   1, i=1, 2, …, n.

And we can get the group ID code as

G_X=X & M                                  (4)

We can get the member ID code as

I_x=G_X ^ X                                   (5)

where “&” is an AND operator; “^” is a XOR operator.

According to the mask code mechanism, the network of search space can form a category tree model which is similar to a computer network structure. Group ID code presents the group ID which the node belongs  to, while member ID code represents the unique identification which can identify the node in this group.

The relations between groups construct a tree. Only the leaf nodes represent the groups where nodes contained in Fig. 4 present a four-layer hierarchical tree model within the way of coding. In Fig. 4, “*”denotes any one of 0 and 1. It means any child node from the branch has the same pattern; n, g and b represent code length, group digits length and branching number, respectively, all of which determine the structure of the tree.

In D-dimension optimization problem, the hierarchical tree distance between nodes i and j in one dimension δ is

                (6)

where Δ(x_bin) operation is to calculate the sum of digits from left to right beginning with the first nonzero number, >0.

The distance between nodes i and j in the whole D- dimension search space is

d_ij=||X_i-X_j||=min{|δ=1, …, D}               (7)

With the strategy above, the one category tree model has been established.

As mentioned before, SWO needs two mapping spaces in order to get two-category tree model. The nodes are categorized by their geographical neighborhoods in the two different spaces. However, not all the mapping methods meet our needs. We have two requirements as follows: Firstly, the two spaces should be bijection and the variable domains in the pair of spaces should be the same. Secondly, to avoid redundancy evaluation, one group member should have little probability in a same group in the other space. In this way, the node has more different contacts in different categories and the searching algorithm has more choices to evaluate new nodes in order to get out of local minimum trap, switching in two spaces.

We introduces Gray and Reverse transform (GRT) strategy combining with Gray transform and Reverse transform in order to comply with the mapping spaces requirements. Gray code is the kind of code that any adjacent Gray code has only one different digit, which means Hamming distance of two adjacent codes equals 1 [27]. Reverse operation means flipping the binary code from high digit to low digit. Gray transform and Reverse transform have the equations as follows:

Suppose binary code B=β_nβ_n-1…β₁ corresponding to gray code G=η_nη_n-1…η₁. g(x) is the binary to Gray code conversion function. It can be expressed as

          (8)

Fig. 4 Binary code in hierarch tree model

The Gray code to binary conversion function can be expressed as

Let r(x) denote the reverse transform function, and we have

r(B)=β₁β₂…β_n, B=β_nβ_n-1…β₁

Thus, the GRT conversion function can be expressed as

f_GRT(x)=g(x)r(x)                               (9)

The GRT adopted will help us establish two mapping search spaces for building a two-category tree model. All the nodes were grouped according to their different geographical neighborhoods in different spaces. We also experimented with chaos mapping space using a logistical equation [28] to iterate by three times. Compared with this, GRT reveals more advantages than chaos mapping space. Figure 5 reveals the relationship of two kinds of mapping spaces. There is an original space with two dimensions in [0, 1]. We use function f=x₁+x₂ to present the color each node closing together.

As shown in Fig. 5, although chaos space brings us the hills terrain and collects some outer nodes into one node’s geographic neighborhood, the smaller local area still remains the same because it keeps continuous. This means that although the chaos contacts are spread around in the original search space to some extent, there are still some closer to it. It is a big opportunity that one group members in different categories will still in the same group. On the contrary, GRT breaks continuously and makes the group members spread around the entire space. With the help of GRT, algorithm can skip out the local optimal with more choices. We can see this phenomenon in Fig. 6. Neighbors in GRT space are widely distributed throughout the original space in order to reduce the probability of duplicate evaluation; however, the chaos space does not do that neatly. There are a lot of neighbors in chaos space still closing together in original space.

Fig. 5 Two mapping solution spaces (Similar color presents that nodes are closing together in original space): (a) Chaos mapping space; (b) GRT mapping space

Fig. 6 Chaos and GRT neighborhoods converting into original space: (a) Neighbors in chaos mapping space; (b) Neighbors in GRT mapping space

Therefore, the network from GRT will help decentralized searching strategy search widely and the small-world network with fast searchable feature has been established by two-category hierarchical tree model with GRT strategy.

3.4 Decentralized search

The process of decentralized searching algorithm contains two steps. The first step is the query operation, which searches and evaluates the contact nodes. The second step is the delivery operation, which chooses the appropriate node that has the minimum value.

According to WATTS’ theory, one node contains two kinds of contacts. First one is short range contacts, which know each other because they are in the same group. The other one is long range contacts, which have certain probability to know each other through different groups. We get short range contacts in the following steps.

In the category tree model, the size of each group is S_mc=(2g-1)^D. Select the number of needed query contacts N_ns≤N_mc. Define the maximum distance between short range contacts as d_sZ⁺.

Randomly generate D length symbol vector S= s₁s₂…s_D, s_i{+, -}, i=1, 2, …, D.

According to the pseudo-code in Fig. 7, one short range contact X  ′ is got, where bit(1) denotes minimum distance units.

Fig. 7 Process for finding short distance neighbor

Repeat Step 2 and Step 3 N_ns times to get the required number of short range contacts.

We get long range contacts in the following steps.

Use roulette approach to select d_i as the distance for X_i to find long range contacts within the probability

Randomly choose one dimension vector of X_i as x_r. Do the 0-1 reverse mutation operation from left n-g-d_i+1 digit to right end;

Generate random distance d_j{1, 2, …, d_i} for each dimension vector x_jX_i, j=1, 2, …, D. Do the 0-1 reverse mutation operation from left n-g-d_j+1 digit to right end;

After the mutation, we get one long range contact  of X_i.

SWO needs to find short and long range contacts in both mapping spaces. All of the contacts in GRT space should be converted back to original space in order to calculate its fitness value.

Delivery operator adopts Milgram’s greedy criterion. The holder i delivers the mail to its contact j which is thought as the closest node to target t of all the contacts including both the original and GRT search spaces. Because an optimization algorithm doesn’t know the target’s location exactly, we choose the highest fitness value of them as the closest node near to target t. We have to claim that in this criterion it cannot guarantee that this algorithm follows the Milgram’s method strictly and achieves the six degrees of separation principle where the average transfer length is proximately around 6 owing to the unknown target address. However, according to the finding short and long range contacts in this rule, the small-world network model has been established which bring us the short average path length coming from its property.

4 Experiment

4.1 Parameters of SWO

The parameters of SWO which need our attentions are as follows: code length n, cluster size m, number of group membership N_mc, and probability parameter of acquaintance α. Parameter n concerns the scale of the problem and the resolution ratio of the search space; m means the size of current mail holders or the generation size in popular terms, and the value is often set between 10 and 40. Specially in SWO, N_mc determines the amount of short range contacts, with which branching number b together fixes the structure of the categories tree model. N_mc is determined by group digits length in binary code and the code’s dimension. Group digits length g is often set as the one-fifth of the code length, and b is usually equal to two in order to get b-tree, but bigger or smaller has not yet been found to harm the algorithm. N_mc directly affects finding the short range contacts; α directly affects finding the long range contacts. When α=0, it has the uniform distribution over long-range contacts. As α increases, the long-range contacts of a node become more and more clustered in its vicinity on the grid. Thus, α serves as a basic structural parameter measuring how widely “networked” the underlying society of nodes is. In our observation, its value is often set between 0.2 and 0.5.

Generally speaking, like other intelligent algorithms as GA, the parameters in coding and clustering are required. To aim at adjusting the ability of exploitation and exploration, we set N_mc for exploitation and α for exploration. The adjustments of two parameters in SWO were tested in this work to survey the influence on optimal ability.

4.2 Performance test in continues benchmark functions

In order to verify the effectiveness of the SWO algorithm (W-SWO) and the effectiveness of different strategies, and compared with the SWO designed with KLEINBERG model (K-SWO), eight classical test functions were used as benchmark, such as the ROSENBROCK function [29], CAMEL function [30], RASTRIGRIN function, SHEKEL’s Foxholes function [31], SCHAFFER’s function, SCHWEFEL’s function [32], SHUBERT function [33] and HANSEN function. The functions listed above are represented according to priority as f₁-f₈, in which f₅ needs the maximum and the rest needs the minimum. f₁ and f₂ are the unimodal functions while f₃-f₈ are the multimodal functions. Using eight test functions in two dimensions, the algorithms (W-SWO and K-SWO) were tested in a computer with a 2.5 GHz CPU and 1 G memory by using Matlab 2009 software.

The parameters are set as follows: code length n= 20, group digits length g=3, branching number b=2, the initial cluster of mails m=10, and the probability parameter of acquaintance α=0.5. The termination condition chose the number of evaluation N_EFs<1×10⁵, or the algorithm was terminated prematurely when the results achieved a given accuracy. Each test function runs 50 times in order to eliminate the computing errors. We compared the W-SWO with K-SWO, in which parameters setting can refer to Ref. [34]. The result is listed in Table 1. It is shown that W-SWO can achieve optimal object 100% in 50 tests and exhibit more stable (in N_EFs,Std.) than K-SWO and fast convergence (in N_EFs,Mean).

We also test the different strategies for finding mapping spaces to verify whether the structure of the small-world network plays an important role in convergence. The two of them are SWO designed with GRT and SWO designed with chaos mapping strategy. Test results of the SWO designed with GRT are shown in GRT column of Table 1. As the comparison, the deficiency of the chaos strategy has been exposed in Object attained column. Except the functions 1 and 2, SWO designed in chaos could not achieve the optimal object 100%. This is because that there is no local extremum in functions 1 and 2 but in others. This means that SWO designed with chaos cannot handle the local extremes as well as SWO designed with GRT. This deficiency has also appeared in N_EFs,Std. and N_EFs,Mean. The result reflects that chaos strategy is more unstable than GRT, affected by the complex of the test functions.

Figure 8 shows the slope of convergence when the algorithm has iterated 625-time test in f₈. The lower the value, the faster the convergence expressed in the iteration. Figure 8 shows that the SWO convergence rates, designed with GRT, decrease gradually from high to low, but generally maintain a relatively rapid speed of convergence and keep a certain rate in the later iterations. However, the SWO convergence speed, designed with chaos, is blocked by local extremum several times, skips out but stops finally after iterated 423 times. The advantage of GRT has been demonstrated during the function test results and comparison.

It is known that in SWO only local information is available for each node to simulate the delivery experiment. In this work, we attempted to consider global information such as each mail’s route, the best node being found so far and all the nodes that have  been evaluated to enrich the reference for the delivery.    The sender will reference both global best and local best nodes to make a sending decision. The improvements may borrow ideas from particle swarm optimization (PSO). We will test it in comparison to reveal whether it is the improvement direction for SWO.

Table 1 Function test results and statistics

Fig. 8 Convergence rate of SWO

In order to test the capability of solving a complex optimization problem with SWO and the influence on the solving results using different strategies of the algorithm in high dimension, the following tactics are taken for complex function testing:

SWOA10: SWO with a cluster of mails but without global information. Cluster size m=10, code length n=20, group members’ code length g=3, branching number b= 2, and acquaintance probability exponent α=0.5.

SWOA10g: SWO with a cluster of mails and global information sharing. Cluster size m=10, code length n=20, group members’ code length g=3, branching number b=2, and acquaintance probability exponent α=0.5. Global information learning factor c₁ and c₂ are equal to 2.

SWOA1: SWO for single mail testing. Cluster size m=1, code length n=20, group members’ code length g= 3, branching number b=2, acquaintance probability exponent α=0.5.

Meanwhile, the same tests for DE, GA and PSO will be conducted to horizontally compare the performance of SWO and those classic intelligent algorithms. Population size of these three algorithms will be m=40, and the other algorithm parameters select the best setting according to Ref. [35].

LIANG et al [36] put forward a novel benchmark for combining complex numeric optimization in SIS2005. This benchmark aims at making tests closer to practical optimization problems. LIANG’s test function has no symmetric points, and many local extrema locate near the optimal value, which requires a higher performance of the optimization algorithm. In the benchmark, CF6 and CF5 are the two most complex functions among them, especially in CF6. LIANG’s test function is also the main algorithm testing platform that many papers adopt.

We used the test benchmark for comparison in 10 dimensions. In order to eliminate the influence of randomness on performance comparison, each algorithm was run 20 times against each test, and final results were recorded upon termination. The terminating condition is that the max evaluation count reaches 1.0×10⁵. Table 2 compares the best result, median value and standard deviation. The rank of the test result comparison for the algorithms is in parentheses.

From the comparison of best results, it can be seen that SWOA10 never gets an optimal value in the test results. SWOA10g finds smaller function values during tests against CF1, CF2, CF3 and CF6 than others. CF4’s function value close to the minimum is found by SWOA1. DE is superior to other algorithms in CF5 tests, and finds the minimum in results. SWOA1 has a good optimization seeking ability, leading to fairly nice results in CF4 and CF1. SWOA10 has the worst optimization seeking ability, far behind the other algorithms.

We can see the median values of test calculation results in Table 2. All the other test functions cannot find optimal solution within specified evaluation times except CF1. In CF1, PSO falls into local optimal value 100 many times during 20 tests, and SWOA10 stops iteration before finding an optimum solution. SWOA10g, SWOA1, DE and GA can find optimum smoothly. Among 6 test functions, SWOA10g has a better solving result than other algorithms, except for CF5. DE has a better solving ability for CF5 than other algorithms. In conclusion, SWOA10g takes the lead for its median value, and SWOA1 is equivalent with DE in performance, while SWOA10 is worse than other algorithms.

According to the comparison of standard deviations, SWOA10 is relatively stable, because its standard deviation is either smaller than that of other algorithms or close to the minimum standard deviation. SWOA10g is the second, as stable in the CF3 test, with an advantage in other function tests over other algorithms. GA and PSO fall into the bottom of the standard deviation comparison, which proves the lack of stability when solving this type of test function result.

Figure 9 displays the box plots of the calculation results from six algorithms running 20 times for each test and against six test functions. It can be seen that SWOA10g is in a quite good position in the test results. SWOA10 has a short box height, but lacks sufficient ability for drilling down, which shows that SWOA10 has good stability but bad optimization seeking ability. SWOA1 shows different properties from different test functions, which means that this algorithm is highly dependent on the test issue itself. The test result of DE shows its algorithm advantage on solutions for all functions especially in tests against CF5, and the only exception is CF6, where solving stability is rather poor. GA and PSO show instability during test process, although their downward seeking ability (best in test results) are better than SWOA10. Equivalent to other algorithms, median line falls behind due to the instability of the algorithms.

Table 2 Results achieved by algorithms on six composition functions

Fig. 9 Box plots of algorithm performance test comparison: (a) CF1; (b) CF2; (c) CF3; (d) CF4; (e) CF5; (f) CF6

In order to illustrate the effect on optimization convergence with different strategies between SWO, the terminating condition or the max evaluation count increases to 5.0×10⁴. Plots in Fig. 10 display test convergence curves of SWOA1, SWOA10 and SWOA10g for six test functions. The X axis is the evaluation count in logarithmic coordinate, and the Y axis is the best value under the current calculation. We can see that SWOA10 exhibits a strong convergence effect from the very beginning, and keeps dynamic in subsequent downward seeking. Due to the initial solution and the properties of the test function itself, SWOA1 has different presentations in each test function. However, a common characteristic is that SWOA1 and SWOA10g both have a strong capability of optimization seeking, which allows them to do a fast search downward seeking for minimum crossing convergence curve of SWOA10 even without better initial cluster. SWOA1 demonstrates SWO’s delivery ability for a single mail. This proves that every mail can search target value fast in a categories tree model network. SWOA10 aims at finding an optimal value with 10 independent mails. Due to allocation of every mail for evaluation limitation, downward seeking ability is fairly poor and convergence is also slow.

Fig. 10 Different strategy’ convergence curves of SWO: (a) CF1; (b) CF2; (c) CF3; (d) CF4; (e) CF5; (f) CF6

According to the results, SWO has a quite larger advantage over GA, DE and PSO in solving complex optimization problems. Furthermore, it is a right way to improve SWO algorithm combined with global information. It is also shown that SWOA1 has a strong

downward seeking ability, but lacks stability. This proves WATTS’s experiment result again that many mails failed achievement [37]. SWOA10 has better stability but performs poorly when solving for an optimum. How to choose a population size for the SWO algorithm should be researched in the later work. If it is too large, mass time will be wasted in the calculation for an optimal solution. If it is too small, it will easily fail into local optimum. We usually choose population size between 10 and 20.

4.3 Performance test in discrete problem PFSP

Permutation flow shop scheduling problem (PFSP) was chosen as the benchmark which is the discrete problem to distinguish from the benchmark in continues in the above section. PFSP [38] is described as: a set of n jobs are going to be processed by a set of m machines with given orders and sequences. The processing time of each job by any machine is known. The task is desired with a minimum of idle time, the minimum of average processing time of each job, a minimum of makespan of each job, a minimum of average waiting time and so on. In this work, the minimum of makespan of each job is set as our target. The items below are assumptions for this problem:

Assumption 1: One job couldn’t be processed at two or more machines at the same time;

Assumption 2: One machine cannot be used by another job when it processes a job;

Assumption 3: It cannot be terminated when a job is processed on a machine;

Assumption 4: The sequence of each machine for a certain machine is given and cannot be changed.

The design for SWO solving discrete problem has been done by HUANG et al [39]. And more benchmark tests in discrete problem can be found in this work. There is no primary difference for SWO design in the continuous and discrete problems, expect coding and grouping strategies.

In this work, 24 of the 120 benchmark problems from easy to difficult are used to test the proposed algorithm, which is put forward by TAILLARD [40]. TAILLARD benchmark test set contains 120 instances of FSP,  and the basic information and best solution of these problems could be found at http://mistic.heig-vd. ch/taillard/.

The No. 1 and No. 5 problems of each test set are selected to conduct our experiment. SWO is used to be compared with MGA [41], NPSO [42], ATPPSO [43] in Table 3. The parameters are set as follows: the number of envelope is 80, the probability of acquaintance of neighbors far away is α=0.4, the iteration is 400, and each instance has been run for 10 times.

The best solution (BS), worst solution (WS), average solution (AS) and best relative error (BRE) are listed in Table 3. V_BRE=(V_BS-V_C*)/V_C*×100, where V_BRE is the value of BRE in Table 3, V_BS is the value of BS, V_C* is the value of best solution which has been found up to now by all the test algorithms. According to the results, the performance of ATPPSO and SWO are almost identical in terms of the BS because SWO is better than ATPPSO in former 17 problems but worse in later 7. But they all achieve the good performance rather than MGA and NPSO. Especially, we can see that the results obtained by SWO are more efficient than any other algorithm in AS, which means it is more stable and most of the test times gain an ideal solution.

Above all, SWO is an efficient algorithm in solving TA compared to other algorithms. We can observe that SWO performs better in all experiments than MGA and NPSO. It can be concluded that SWO has great potential to solve discrete problems.

4.4 Contribution efficiency of four kinds of contacts

This test also compares the contribution efficiency of the four kinds of contacts. The contribution means the times of SWO finding a better node according to each kind of contact relationship. Figure 11 shows the different contributions of four kinds of contacts to the algorithm, such as short range contact in the original space (real-short), long range contact in the original space (real-long), the short range contact in GRT space (Gray-short), and long range contact in GRT space (Gray-long). It reflects the active times of contribution τ and the convergence ratio ν between the four types of contacts in the 10 000 evaluation calculations. Convergence ratio ν is equal to the division of the value of total improvement φ and contribution times τ. It can be seen that the times of contribution of the original search space contacts is far greater than that of the GRT space, and the times of short contacts are more than the long contacts. The contribution rate to the algorithm of the contacts in GRT, however, is greater than that of the contacts in the original search space. And the convergence efficiency of the long range contacts is greater than that of the short range contacts.

These test results can help us to establish the way of obtaining the optimal target by finding contacts in the order as searching from GRT space to original space, from long range to short range contacts. When a better node is found than current holder we pass the mail to the better node in order to get a not bad jump in highest efficiency.

4.5 Influence of parameters adjustment

In this subsection, the setting of different parameters is tested in order to verify the efficiency of SWO for target, deliver immediately. With this strategy, the algorithm will approach to the target step by step with solving optimal problem which has indeed been influenced by them. It has been mentioned in Section 4.1 that there are two important contacts for searching short-range contacts and long-range contacts. They represent the exploitation and exploration, respectively. We have N_mc for exploitation and α for exploration. N_mc= (2^g-1)^D, is the group size, which means that all those members in the group are short-range contacts; g is the group digits length in a code as shown in the coding rules; D is a constant value as the dimension of the problem. So, the value of g decides the definition of short-range in solution space; α is the acquaintance parameter, which decides the definition of long-range in solution space. If α grows up, two nodes only meet with in short distance. On the contrary, if α grows down and near to zero, nodes have the same probability to connect with each other. This will generate a uniform random graph.

Table 3 Results achieved by algorithms on TAILLARD benchmark test

Fig. 11 Contributions in SWO of four different types of neighbors

Two parameters adjustments in SWO have been tested to survey the influence on optimal ability: one is g from 2 to 4 in Step 1, and the other is α from 0 to 1 in Step 2. All the tests go in benchmark f₅ from SIS2005 and each combination of the two parameters runs 20 times with maximum N_EFS lower than 1.0×10⁵.

The best solution has been recorded which has been found by SWO in different parameters combination in each run. The results are presented in Fig. 12. The middle line indicates the middle value of 20 runs. The span of the box indicates the stability of the results. The smaller the box, the more stable the result is. Note that, in each column, with the same g, different values of α affect the efficiency of decentralized search in this network model. When α is set to be 0.2, 0.4 and 0.6, the middle lines are lower than others, especially 0.2-0.4 in this function optimization. Meanwhile, it has exhibited the stability because it almost results in 20 runs near to the optimal solution without failure. This means the mails have been well delivered under the guidance of the small-world network. However, when α goes down to 0, evolving into a uniform random graph, or goes up to 1, evolving into regular lattice graph, the convergence ability declines obviously. The random graph connects very two nodes randomly, which disturbs the small-world properties and weakens the guidance for finding optimum. Worse than this, in regular lattice  graph, all the envelopes walk a small pace in one iteration and easily fall into prematurity because of the long average graph length. In turn, the results with higher than 0.6 of α perform worse than the results with lower than 0.2. This reflects that, in solving function f₅, values are between 0.2 and 0.6 because α will bring a high efficiency, while smaller or bigger will decline as shown with bad and unstable results. To concentrate on the g value, we observe that there is no obvious change for different g values from 2 to 4. In our opinion, because this SWO adopts drawing certain numbers from short-range contacts for rating, the group size change will not cost the evaluation time for short-range contacts. In this function f₅ test, g=3 and α=0.4 gain the best setting for optimization. The convergence curves for setting of different parameters are shown in Figs. 13-15. We can see when the α is from 0.2 to 0.4, SWO gets fast convergence as down quickly in early iterations. These results further explain the reason of the fast convergence as well as the high success rate of the SWO.

 

Fig. 12 Best values of SWO found in f₅ for each of parameter combination over 20 runs: (a) g=2; (b) g=3; (c) g=4

Fig. 13 Convergence curve in solving f₅ for each of parameter combination when g=2: (a) α=0; (b) α=0.2; (c) α=0.4; (d) α=0.6; (e) α= 0.8; (f) α=1.0

Fig. 14 Convergence curve in solving f₅ for each of parameter combination when g=3: (a) α=0; (b) α=0.2; (c) α=0.4; (d) α=0.6; (e) α= 0.8; (f) α=1.0

Fig. 15 Convergence curve in solving f₅ for each of parameter combination when g=4: (a) α=0; (b) α=0.2; (c) α=0.4; (d) α=0.6; (e) α= 0.8; (f) α=1.0

5 Conclusions

1) Because nodes in this network can easily communicate with each other, this algorithm is suitable for heuristic methods to search targets efficiently .

2) If the test mail converges to a local trap in one space, the auxiliary mapping space can help it jump out of the local minimum in most situations.

3) This architecture has fully revealed the properties of exploitation and exploration which reflects the common feature of intelligent algorithms. There are also related parameters to adjust and control. It makes the setting of them easy and direct and also simply for researchers to analyze.

4) The algorithm studies the rapid optimization in the way of the network topology construction, so that the architecture has a good combination properties with other intelligent methods.

5) Furthermore, the architecture of SWO is more adoptable for further improvement. In the future, as our next work, research of SWO algorithm should be focused on investigating the improvement of the robustness through sharing global information, combining with other algorithm, adopting in more realistic problem in engineering and so on.

Acknowledgments

Special thanks to Mr. HUANG Gang, for a lot of ideas and supports from his work.

References

[1] LINHARES A. preying on optima: A predatory search strategy for combinatorial problems [C]// Proceedings of the Proc IEEE Int Conf Syst. San Diego, CA, USA: IEEE, 1998, 8(11/12/13/14): 2974-2978.

[2] SUN Yi, DAAN W, TOM S, JUERGEN S. Efficient natural evolution strategies [C]// Proceedings of the 11th Annual Conference on Genetic and Evolutionary Computation (GECCO ′09). New York, USA: ACM, 2009: 539-546.

[3] HOLLAND J H. Adaptation in natural and artificial systems: An introductory analysis with applications to biology, control, and artificial intelligence [M]. Ann Arbor: University of Michigan Press, 1975: 1-211.

[4] SU Guo-shao, ZHANG Xiao-fei, CHEN Guang-qiang, FU Xing-yi. Identification of structure and parameters of rheological constitutive model for rocks using differential evolution algorithm [J]. Journal of Central South University of Technology, 2008, 15(s1): 25-28.

[5] ANAGNOSTOPOULOS A, MICHEL L, VAN P, VERGADOS Y. A simulated annealing approach to the traveling tournament problem [J]. Journal of Scheduling, 2006, 9(2): 177-193.

[6] GLOVER F. Heuristics for integer programming using surrogate constraints [J]. Decision Sciences, 1977, 8: 156-166.

[7] MAHDIYEH E, HUSSAIN S, AZAH M. Power system stabilizer design using hybrid multi-objective particle swarm optimization with chaos [J]. Journal of Central South University of Technology, 2011, 18(5): 1579-1588.

[8] DORIGO M, MANIEZZO V, COLORNI A. Ant system: Optimization by a colony of cooperating agents [J]. IEEE Trans Syst Man Cybern B Cybern, 1996, 26(1): 29-41.

[9] KARABOGA D, BASTURK B. A powerful and efficient algorithm for numerical function optimization: Artificial bee colony (ABC) algorithm [J]. Journal of Global Optimization, 2007, 39(3): 459-471.

[10] GU Yun-li, XU Xin, DU Jie, QIAN Huan-yan, Optimization algorithm based on artificial life algorithm and particle swarm optimization [C]// Second International Conference on Information and Computing Science. Manchester: IEEE Press, 2009: 173-176.

[11] NGUYEN T T, YAO X. An experimental study of hybridizing cultural algorithms and local search [J]. Int J Neural Syst, 2008, 18(1): 1-17.

[12] MASSIMO F, RONALD M. Navigation in small-world networks: A scale-free continuum model [J]. Journal of Applied Probability, 2006, 43(4): 1173-1180.

[13] TRAVERS J, MILGRAM S. An experimental study of the small-world problem [J]. Sociometry, 1969, 32(4): 425-443.

[14] WATTS D J, STROGATZ S H. Collective dynamics of ‘small-world’ networks [J]. Nature, 1998, 393(6684): 440-442.

[15] STROGATZ S H. Exploring complex networks [J]. Nature, 2001, 410(6825): 268-276.

[16] KLEINBERG J M. The small-world phenomenon: An algorithmic perspective [R]. Cornell Computer Science Technical Report. New York: ACM, 1999: 163-170.

[17] WATTS D J, DODDS P S, NEWMAN M E J. Identity and search in social networks [J]. Science, 2002, 296(5571): 1302-1305.

[18] WALSH T. Search in a small world [C]// Ijcai-99: Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence. San Francisco: Morgan Kaufmann, 1999: 1172-1177.

[19] CHEN Jian-zhen, LIU Wei, ZHU Jian-yang. Two-dimensional small-world networks: Navigation with local information [J]. Phys Rev E, 2006, 73(5): 56111-56117.

[20] CUI Zhi-hua, CHU Yong-fang, CAI Xing-juan. Nearest Neighbor Interaction PSO Based on Small-World Model [J]. Intelligent Data Engineering and Automated Learning, 2009, 5788: 633-640.

[21] DU Hai-feng, ZHUANG Jian, ZHANG Jin-hua, WANG Sun-an. Small-world phenomenon for function optimization [J]. Journal of Xi’an Jiaotong University, 2005, 39(9): 1011-1015. (in Chinese)

[22] LI Xiao-hu, ZHANG Jin-hua, WANG Sun-an, LI Mao-lin, LI Kun-peng. A small world algorithm for high-dimensional function optimization [C]// Proceedings of the 8th IEEE International Conference on Computational Intelligence in Robotics and Automation (CIRA'09). Piscataway, NJ, USA: IEEE Press, 2009: 55-59.

[23] WANG Shuang-xin, LIU Hai-rui, DONG Yang. Constrained model predictive control based on chaotic small-world optimization algorithm [C]// Proceedings of the 18th IFAC, World Congress, Milano, Italy, 2011: 134-142.

[24] YANG Xin-yan, WANG Xiao-hua. Decentralized small-world optimization strategy [J]. Journal of Suzhou University: Engineering Science Edition, 2007, 3(11): 41-46. (in Chinese)

[25] WANG Xiao-fan, LI Xiang, CHENG Guan-rong. Complex network theory and its applications [M]. Beijing: Tsinghua University Press, 2006: 46-52. (in Chinese)

[26] KLEINBERG J M. Navigation in a small world—It is easier to find short chains between points in some networks than others [J]. Nature, 2000, 406(6798): 845.

[27] SHARMA B D, KHANN R K. On m-ary Gray codes [J]. Information Sciences, 1978, 15(1): 31-43.

[28] ZHAO Cheng-lin, SUN Xue-bin, SUN Song-lin, JIANG Ting. Fault diagnosis of sensor by chaos particle swarm optimization algorithm and support vector machine [J]. Expert Systems with Applications, 2011, 38(8): 9908-9912.

[29] PRICE K V. Differential evolution: A fast and simple numerical optimizer [C]// 1996 Biennial Conference of the North American Fuzzy Information Processing Society. Nafips: IEEE Press, 1996, 524-527.

[30] EBERHART R C, SHI Y. Comparing inertia weights and constriction factors in particle swarm optimization [C]// Proceedings of the 2000 Congress on Evolutionary Computation. La Jollai: IEEE Press, 2000: 84-88.

[31] JIAO Li-cheng, DU Hai-feng, LIU Fang, GONG Mao-guo. Immunological computation for optimization, learning and recognition [M]. Beijing: Science Press, 2006: 58-118. (in Chinese)

[32] LEUNG Yiu-Wing, WANG Yu-ping. An orthogonal genetic algorithm with quantization for global numerical optimization [J]. IEEE T Evolut Comput, 2001, 5(1): 41-53.

[33] MADSEN K. Nonlinear approximation and engineering design [EB/OL]. [2006-12-21]. http:\\www2immdtudk\~km\GlobOpt\ testex\testproblemshtml.Denmark.

[34] DU Hai-feng, WU Xiao-dong, ZHUANG Jian. Small-world optimization algorithm for function optimization [J]. Advances in Natural Computation, 2006, 4222(2006): 264-273.

[35] FANG Wei, SUN Jun, XU Wen-bo. A new mutated quantum-behaved particle swarm optimizer for digital IIR filter design [J]. Eurasip J Adv Sig Pr, 2009, 2009: 367465.

[36] LIANG J J, SUGANTHAN P N, DEB K. Novel composition test functions for numerical global optimization [C]// 2005 IEEE Swarm Intelligence Symposium. Pasadena: IEEE Press, 2005: 68-75.

[37] DODDS P S, MUHAMAD R, WATTS D J. An experimental study of search in global social networks [J]. Science, 2003, 301(5634): 827-829.

[38] JARBOUI B, IBRAHIM S, SIARRY P, REBAI A. A combinatorial particle swarm optimization for solving permutation flowshop problems [J]. Computers & Industrial Engineering, 2008, 54(3): 526-538.

[39] HUANG Gang, TIAN Zhi-peng, SHAO Xin-yu, LI Jin-hang. Small world optimization for multiple objects optimization of mixed-model assembly sequencing problem [M]//GRZECHCA W. Assembly Line- Theory and Practice: Intech, 2011: 131-148.

[40] TAILLARD E. Benchmarks for basic scheduling problems [J]. European Journal of Operational Research, 1993, 64(2): 278-285.

[41] RUIZ R, MAROTO C, ALCARAZ J. Two new robust genetic algorithms for the flowshop scheduling problem [J]. Omega, 2006, 34(5): 461-476

[42] LIAN Zhi-gang, GU Xing-sheng, JIAO Bin. A novel particle swarm optimization algorithm for permutation flow-shop scheduling to minimize makespan [J]. Chaos, Solitons & Fractals, 2008, 35(5): 851-861.

[43] ZHANG Chang-sheng, NING Jia-xu, OUYANG Dan-tong. A hybrid alternate two phases particle swarm optimization algorithm for flow shop scheduling problem [J]. Computers & Industrial Engineering, 2010, 58(1): 1-11.

(Edited by DENG Lü-xiang)

Foundation item: Projects(51105157, 50875101) supported by the National Natural Science Foundation of China; Project(2009AA043301) supported by the National High Technology Research and Development Program of China

Received date: 2011-06-28; Accepted date: 2011-10-21

Corresponding author: LI Jin-hang, PhD; Tel: +86-27-87543024; E-mail: jinhangli@gmail.com