There are many proven algorithms to solve discrete sequencing problem and we commonly use the heuristic algorithms such as Ant Colony Algorithm and Genetic Algorithm. When solving the discrete sequencing problem, the Ant Colony Algorithm may be convergence to local optimum and the Genetic Algorithm has low solving efficiency as producing a lot of redundancy iteration by using insufficient feedback information. Therefore, we need an algorithm which has a strong capability of global searching and fast convergence speed.
Small World Optimization just meets our requirements.
The research on small world firstly originates in 1929 by a Hungarian writer F.Karinthy. He put forward the theory “Any two people on earth can be contacted through a chain composed
138
by five other persons” (Braun, 2004). In 1967, S.Milgram confirmed the small world phenomenon through the famous letters delivery experiments and proposed six degrees of separation theory (Travers & Milgram, 1969). With the study on small world effect by Watts and Strogatz (Watts & Strogatz, 1998; Strogatz, 2001), small world phenomenon was gradually valued and quickly became a hot spot of complex system and complexity theory research.
This paper designed a fast search algorithm called Small World Optimization (SWO) which was inspired by the hierarchical categorization tree model and multi categories method based on small world theory. The solution space can be divided into the hierarchical categorization tree model using hamming distance. Two bijective mapping solution spaces were adopted to establish multi categories method. Small World Optimization evaluated the relationship between nodes of the short and long distance neighbors in the two spatial networks and put the envelopes to the target, and then found the optimal solution.
3.1 Designing small world optimization 3.1.1 Basic idea of small world optimization
The basic ideas of Small World Optimization: simulating Milgram’s letters delivery experiments (J.Travers & S.Milgram, 1969), first deliver several envelopes from different places in the solution space and regard each envelope holder (node called in this paper) as a candidate solution; then find out each node’s best node which is estimated by objective function and deliver the envelope to this node; at last, each envelope will be closer to the object node through multiple delivery in the small world network.
The extensive research on small world effect also makes Small World Optimization achieve excellent results in solving actual problem. Huang (Huang et al., 2011) made a deep research on Small World Optimization and designed a fast search algorithm for continuous problem.
With some test of standard continuous problems for Small World Optimization, Small World Optimization has fast convergence ability. Inspired by the Small World Optimization on continuous problem, we study the solving strategy of Small World Optimization in discrete problem.
3.1.2 Definition of short and long neighbors
For problems of continuous type, we can easily use network address division method to solve the hierarchical structure of the solution space. The relationships between the different addresses of the same subnet network are short neighbors. But the addresses of different subnet networks have long neighbor relationships.
However, sequencing problem is a kind of discrete problem for which we can’t apply Internet Protocol division rules in continuous problem because each solution is a sequence.
Normally, hamming distance is used to express the distance between different sequences of discrete problem. So the two sequences between which the hamming distance is 2 are defined as short neighbor relationship. The number of short neighbors of a sequence node isCn2 in a sequence of length n. Such as sequence 1 2 3 4 5 and sequence 1 3 2 4 5 have short neighbor relationship. If hamming distance of two sequences is greater than 2, they have long neighbor relationship.
Acquaintance probability of any two long nodes is expressed by index functionedij, is acquaintance index anddi j is the hamming distance of two long nodes. From the function, we realize that the smaller the hamming distance, the greater the acquaintance probability, and vice versa.
139 3.1.3 Construction of multiple space conversion
The highlight of small world optimization algorithm is multiple space synchronization search, solving multiple space mapping is a key problem. According to the above discussion, Small World Optimization can find the best solution through searching in double spaces which combine two bijective mapping solution spaces with original solution spaces.
1. Discrete space similar conversion rules of gray yards
For discrete problem, sequence is usually described as real integer. Such as, for a Flow shop problem with 5 workpieces, workpieces sequence A, B, C, D, E is corresponded with 1, 2, 3, 4, 5 respectively.
Adjusting the workpieces sequence will get a new solution; we define all the solution as the first heavy solution space. The second heavy solution space is from the first heavy space through some conversion rules. According to the conversion rules of binary gray yards for continuous space, we design a similar conversion rule for discrete space, the conversion code rules are as follows:
Conversion rules. For a sequenceX1 2 3 4 5, its lengthM5, conversion procedure below:
i. According to the conversion rules of gray yards, first consider shifting the sequence coding, circularly shift Nbyte rightward. IfN2, the sequence will beX14 5 1 2 3.
ii. In order to increase the differences between the original sequence and new sequence and enlarge its hamming distance length, we can reverse the original sequence, and the sequence will beX23 2 1 5 4.
iii. According to the two sequences which take exclusive by bitwise operation in gray yards conversion, we can do the same operation in discrete sequence. For sequence 3 2 1 5 4, if overall addm, then take more to the sequence lengthM. Gi(Xi m 1)%M1. Ifm1, the sequence will beG4 3 2 1 5.
Fig. 1. The procedure of conversion rules
2. The conversion of gray yards for discrete space
In order to make discrete sequence fully meet the conversion of gray yards, first the real integer will be converted to binary coding. For a sequence 2 5 4 3 1, respectively convert the real integer sequence to binary coding of which length is 3. As Fig. 2 (a) describes.
Then we get a new binary coding sequence by conversion of gray yards to the binary coding sequence. At last, convert the binary coding to integer coding and get the final sequence as Fig. 2(b):
140
Fig. 2. The binary conversion of Real integer
Usually we can correct the sequence by Smallest Order Value rule, the sequence will be: 3 5 4 2 1.In fact, we don’t have to correct the final sequence, because we only get the second heavy space for finding short neighbor nodes. So, for the sequence 3 7 6 2 1, we can do nothing. The sequence 6 7 3 2 1 is a short neighbor node, which will be 4 5 2 3 1 after converting to the first heavy space.
3.1.4 Updating of the envelope node
According to above definition, for a sequence whose length isN, the number of its short neighbor node is CN2 and the number of its long neighbor nodes isANNCN2 1.
Each envelope holder will search part of its short neighbor nodes and long neighbor nodes in double space and find a better envelope by some rules to update it. General selection rules have two kinds: the first is only finding a better envelope to update; the second is searching specific number of long and short neighbor nodes in double space and finding the best envelope to update.
3.2 Summarizing the procedure of small world optimization The process of Small World Optimization is as follows:
1. Set iterative counterc0;
2. Create initial envelope population Q t( )0 : build the mapped relationship between solution space and coding style according to the constraint definition, randomly select envelopes as the initial nodes.
3. Inquire the neighbor nodes: A certain number of short and long neighbor nodesn are inquired for each envelope node. The inquired neighbor nodes include the nodes coming from the original solution space and the mapping space.
4. Evaluate the neighbor nodes of each node: calculate the evaluation function for each neighbor node, and sort them.
5. Deliver envelope: select a envelope node which better than the current envelope node, then delete the current envelope node. The selection strategy have two kinds: one is calculating all the selected neighbor nodes and selecting the node with best evaluation value. The other one is calculating the evaluation value of each node from this space, and delivering the current envelope node since it’s easy to find high quality nodes in the mapping space. When appearing a better node, stop calculation.
6. Determine whether meet the terminal conditions: if it meets, stop searching and print the result; else, keeping seaching.
141 7. Update all envelope nodes: when all envelope nodes have compete their dilivering, the
nodes compose a new envelope group, and can get Q t( 1). 8. c c 1, return to procedure 3).
The parameters needed in Small World Optimization: the length of coding isn; the number of short neighbor nodes ismc; the acquaintance index of two long neighbor nodes is; the number of envelope nodes ism.
Here, nis equal with the length of sequence and the problem will be more complex when nlargen. The number of short neighbor nodes decides the efficiency and quality of search.
is an important parameter to select long neighbor nodes and generally the range from 0.4 to 0.6. Usually the number of envelope nodes is range from 10 to 40.
Fig. 3. The flowchart of Small World Optimization algorithm
142