Abstract
This work introduces an optimization algorithm based on Bohr’s atomic model. Microcosm of physics and chemistry such as excitation and de-excitation of electrons in atom and bond formation phenomenon are the key mechanism of this algorithm. Performance of proposed algorithm is analyzed with six standard benchmark functions. Results are compared with three competitor algorithms. Results indicate competency of the proposed algorithm in generating good quality solutions with high convergence rate. Proposed algorithm is also applied to real life applications and examined comparative performance with respect to existing implementation of optimization techniques.
Introduction
Optimization is a process of finding the best one or most favorable one from a collection or set of values based on some predefined objectives. Generally, the element that claims either maximum or minimum value of the collection in terms of pre-defined objectives is considered as the best one. Any problem seeking for best solutions can be depicted as optimization problem. An optimization problem can be defined as to find a set of parameters x = (x1, x2, . . . , x n ) that optimizes (minimizes or maximizes) an objective function f (x). Best solution or function value obtained for any optimization problem is referred as optimal solution or optima. An optimization problem may have several optimal solutions in some regions within the solution domain. These optimal solutions are called local optima or local optimal solution and problem is referred as multi-modal optimization problem. Optimal solution of all local optima is referred as global optima. The optimization problems that require to optimize multiple objective functions are referred as multi-objective optimization. In this paper we will deal only with single objective optimization problems.
Almost all domains of science and engineering are confronted with optimization problems. Hence, optimization problems need to solve efficiently and effectively. Although some mathematical approaches such as Linear Programming (LP) [1], Non-linear Programming (NLP) [2] and Dynamic Programming (DP) [3] were developed for solving optimization problems, due to some drawbacks [4] these approaches losses their popularity. Optimization problem that has requirement of finding the global optimal solution is called global optimization problem. Numerous algorithms have been developed since early 1970s. Most of them are inspired by nature. These techniques includes: Evolutionary Algorithms (EA) [5], Genetic Algorithm (GA) [6], Particle Swarm Optimization (PSO) [7], Ant Colony Optimization (ACO) [8] etc. Apart from these nature inspired methods some chemical and physical phenomenon based algorithms are also developed. Chemical phenomenon based algorithm Simulated Annealing (SA) [9] was very popular since its proposal. Physical phenomenon based algorithms have drawn attention these days [10]. The Newton’s gravitational law and the laws of motion based algorithms such as Central Force Optimization (CFO) [11], Gravitational Search Algorithm (GSA) [12], Artificial Physics Optimization (APO) [13], and Gravitational interactions optimization (GIO) [14] are the emerging developments.
Our nature being the great source of inspiration to solve optimization problems as well as improvisation of existing one. Popular algorithms such as GA and PSO have undergone numerous changes in last decades. After proposal of Holland, GA has been further developed by Goldberg [15, 16]. Most promising variant of GA is introduced by Srinivas and Patnaik [17], where probability of crossover (P c ) and probability of mutation (P m ) are adjusted based on fitness values of solution. In recent years lot of improvement to PSO has been proposed with various parameter tuning approaches. Shi and Eberhart proposed PSO with Time Varying Inertia Weight (PSO-TVIW) [18], which improves performance of PSO by varying the value of inertia weight. Another variant is PSO with Random Inertia Weight [19], where random inertia weight is used instead of variation with time. Ratnaweera et al. [20] proposes PSO with Time Varying Acceleration Coefficients using time varying inertia along with time varying cognitive acceleration coefficient as well as both coefficients. Cleric and Kennedy introduced constriction parameter χ, which serves as an alternative to V max . Several types of constrictions such as Type 1, Type 1′ and Type 1″ has been proposed in [21]. Recently, Zhan et al. [22] introduced orthogonal learning mechanism to PSO. Though, orthogonal learning PSO improves solution quality, but requires more computation time [23]. In the same line of work, Differential Evolution (DE) approaches such as jDE [25] also evolved. In [29], showed jDE performs better than other variants of DE algorithms. Although these algorithms have gained wide acceptance in last decades, no free lunch theorem [26] states that non of the optimization algorithm is better in all of the aspects. Hence, there is always need of new algorithms as well as improvement of existing one to solve real world optimization problems more efficiently. In this paper we have proposed a nature inspired heuristic for solving optimization problems, incorporating excitation and de-excitation mechanism of atom. We refer our method as Atom Stabilization Algorithm (ASA).
Remainder of the paper is organized as follows: Section 2 explains motivation and inspirational phenomenon acting behind the proposed algorithm. Section 3 describes background and representational aspects in detail. Section 4 elaborates proposed method with pseudo codes of each of the three operators. Section 5 illustrates convergence mechanism of ASA with suitable examples. Section 6 analyzes comparative performance of ASA. Section 7 explains real life application of ASA. Finally, concluded in Section 8.
Motivation
Atom undergoes structural changes by manipulating its valance electrons. Aim of this structural change in atom is to become more stable. This kind of structural change depends on the environment where the atom lies. An atom experiencing different environment may attain different structures to become stable. Notion of these structural changes in atoms are similar to the searching of optimal solution in optimization problems. Process of structural change in atom can be resembled with optimization (process of finding the best one). The environment where atom lies can be resembled with problem domain of optimization problem and the stable structures can be resembled with optimal solutions. These explicit resemblance are the key motivation behind the proposed algorithm. A set of atom is considered to materialize the concept of stable state of atom in the proposed algorithm. Each atom in this set represents as a solution to any optimization problem. Objective is to find stable state of any of these atoms’ which will be the best solution of the corresponding problem. Searching of stable state of atoms in the set is done by strategically manipulating their structure.
Representational aspects and framework
Similar to Bohr’s atomic model, each atom comprises shells where electrons reside. Each shell can comprise only one electron. Each shell is associated with an specific energy level as discussed in previous section. Electrons present in each shell possesses certain amount of potential energy. Inner most electrons have the higher energy where as outer most electrons have comparatively lower potential energy. Presence of an electron is represented with bit one and absence of an electron is represented with bit zero. These bits are referred as electron bits (or bits) and henceforth we will use both these terms interchangeably throughout the paper. For example bit string 1011 represents electrons present at 1st, 2nd and 4th position or electrons present at 1st, 3rd and 4th shell. State of this particular atomic structure will look like as in Fig. 1. As shown in the Fig. 1, nth bit will be the (m - n) th shell where m is the maximum number of bit used for representation. Potential energy of this particular atomic structure is calculated as follows:
The amount in Equation 1 is the negative energy that binds these electrons present in the hypothetical atom presented as bit string 1011. In more general, in this conceptual atomic model potential energy at energy level k of atom a
i
is computed as follows:
Here, S
max
is the maximum number of shells in atoms. As kth shell is the (S
max
- k) th bit in the atomic representation so the potential energy of jth electron bit can be computed as follows:
Hence total potential energy of atom a
i
is computed as follows:
This implies the decimal value of an atomic representation. So potential energy of atom a
i
can be expressed as:
The proposed algorithm comprises three operators as shown in Fig. 2. First operator is named as Excitation. The role of this operator is to excite electron bits from lower energy level to higher energy level or in other words electron bit jumps from inner shell to outer shell. To furnish excitement of an electron, significant amount of positive energy (photon) is supplied strategically to the system from outside. Depending on the positive energy applied some of electron bit excites to any higher energy level or escape from the atom. Second operator is named as Rehabilitation. The role of this operator is to rehabilitate electron bits again to the lower energy level depending on the stability (fitness) of atom. If an atom attains better state (better fitness) after excitation it retains on the excited state, whereas atoms attained worse state de-exited to nearby the previous state. Third operator is named as Alternation. Role of this operator is to attract oppositely charged atoms and form bonds among them to attain more stable state.
Similar to other population based algorithms, ASA is also initialized with randomly generated population of atoms. Iteratively apply excitation operator, rehabilitation operator and excitation operator sequentially. Two versions of ASA are proposed. First one is ASA-I, in which alternation operator is not used. Second one is ASA-II, where number of outermost shells are considered to perform alternation operator. Pseudo code of ASA is given as in Algorithm 1.
flag← 0 (for ASA-I) or 1 (ASA-II)
A← probability of alternation for ASA-II
while termination condition not met
Excitation ()
Rehabilitation ()
if flag = 1
R ← rand ()
if A > R
Alternation ()
end if
end if
fit← evaluate stability of each atom (fitness) end while
Excitation
This operator disrupts the stability of atom. Notion of this disturbance is to look around for better solution (stable state). Main aim of this operation is to reduce the potential energy of atom. When an electron bit excites to any higher energy level potential energy reduces, which implies more stable state than previous one. Each atom is exercised with a distinct amount of positive energy so that the electron bits of particular atom can excite to its highest possible energy level or if gains enough energy it can escape from the atom. External positive energy to be applied to an atom for excitation is computed with the help of current fitness of each atom. Pseudo code of Excitation is given as in Algorithm 2. A normalized fitness (nfit) corresponding to all the atoms are computed. This normalization ensures that atoms with better fitness than the middle atom (in terms of fitness) will try to attain optimal state, whereas atoms with fitness less than middle atom will try to attain state of middle atom. Now randomly select some of the electron bits for excitation and apply positive energy (E pos ). With application of E pos amount of positive energy, whether an electron bit will escape from the atom or excite to any higher energy level is depends on the work function (φ) of the atom. At least φ amount of positive energy is needed to escape an electron bit from an atom. Hence, φ is depicted as escape energy of an atom in this particular.
φ← threshold value for escaping electrons from atom
C← constant value
for each atom a i , i = 1, 2, . . . , n
if fit (a i ) < median (fit)
else
end if
ones← select p bit positions whose bit values are 1
for each bit position j ∈ p
E pos ← rand () + e-nfit(a i )
if E pos > φ
E potExcite (a i ) ← E pot ∓ 2S max -j-1
else
k← select random bit position outer than j and whose bit value is 0.
ifE excite < E pos
E potExcite (a i ) ← E pot ∓ 2S max -j-1
else
E potExcite (a i ) ← E pot
end if
end if
end for
end for
Rehabilitation
This operator negotiates the negative effect of the excitation operator. During excitation of electron bits, state of the atom changes or in other words explore the search domain. Disturbance generated in the system during excitation is temporary. Unfruitful excitations are negotiated during rehabilitation. After rehabilitation of electron bits move back to the original position or any lower energy level whichever is suitable and become stable. Unlike excitation operator in this case external is not applied for de-excitement of excited electron bits. Pseudo code of Rehabilitation is given as in Algorithm 3. If an atom reaches better state after excitation, it retains the state. Otherwise, whether an atom is to rehabilitate or not, is decided with a probability parameter NRh (probability that not to rehabilitate). If probability is less than NRh, the atom will directed towards any better state with the influence of the previous best atom. If probability is greater than NRh, then the atom will rehabilitate. For rehabilitation randomly select shell whose bit values are zero (0 bit). The probability parameter E m determines whether the selected shell of the atom has to rehabilitate electron bits from outside atom or from any higher energy level within the atom. If the probability is less than E m , the atom will rehabilitate electron bit from outside atom. If the probability is greater than E m , the atom will rehabilitate electron from any higher energy level.
NRh← set probability of not to rehabilitate
E m ← set probability of emission
fit old ← before excitation, fit new ← after excitation
for each atom a i , i = 1, 2, . . . , n
R ← rand ()
if fit new (a i ) < fit old (a i )
E pot (a i ) ← E potExcite (a i )
els ifNRh > R
E pot (a i ) ← E potExcite (a i ) + NRh × R × (E pot (a best ) - E potExcite (a i ))
else
zeros← select q bit positions whose bit values are 0
for each bit position j ∈ q
if E m > rand ()
E pot (a i ) ← E potExcite (a i ) ±2S max -j
else
k← select random bit position inner than j and whose bit value is 1.
E pot (a i ) ← E potExcite (a i ) ± (2S max -k - 2S max -j)
end if
end for
end if
end for
Alternation
Electrons present at outermost shell of an atom are generally referred as valance electrons, which participates during bond formation. When an atom release electrons, it become positively charged (cations) and when gain electrons, it become negatively charged (anions). In this hypothetical system, the atom which contains bit 0 in outermost shell is considered as anion, with the similar sense that the bit will become 1 after gaining electron bit. Similarly, the atom which contains electron bit (bit 1) outermost shell is considered as cation after releasing electron bit. This concept is generalized for other shells instead of considering only outermost shell. For any randomly selected shell, if bit is 0 then considered as anion and if bit is 1 then considered as cation.
Atoms in this hypothetical system are displaced depending on their ionization. Highly positive charged atoms (cations) or the atoms having high potential energy and have electron bit in outer shell are more likely to release the outer electron bit and become stable. Similarly, highly negative charged atoms (anions) or the atoms having high potential energy and does not have electron bit in the outer shell are more likely to gain electron bit and become stable. Due to this kind of desire positively charged atoms are attracted towards the negatively charged atoms as shown in Fig. 3. To materialize this attraction into proposed strategy, atoms in the system are rearranged. Highest negatively charged atom is placed in 1st place, 2nd highest atom is placed in 2nd place and so on up to the rth place. Remaining (n - r) atoms of n atoms having positively charged are placed as: Highest positively charged atom is placed in nth place 2nd highest atom is placed in (n - 1) th and so on up to the (r + 1) th place as shown in Fig. 4. Implication of Alternation operator is illustrated as in Algorithm 4.
s← randomly choose a shell from certain percentage of outer shell positions
Rearrange atoms considering s as valence shell of all atoms
Exchange bit values depending on potential energy and charge up to pairing position
Assurance of convergence
In Bohr’s model when atoms excited to any higher energy level then the potential energy increases but in this case increasing or decreasing is depends on the objective function. If the goal is to minimize an objective function then the potential energy will decrease and otherwise it will increase with excitation of electron bit. Since increasing and decreasing of potential energy directly effects increasing and decreasing of the objective function value so the excitation of electron bit to any higher energy level ensures the convergence towards the optima. However, it may possible that even if potential energy decreases the objective function value may increase. As shown in the Fig. 5 suppose we have to minimize the function f (x) = sin (x), say current position is x2 = 46 is represented with bit string 00101110. After excitation of 3rd bit of 00101110 to 1st bit position we have 00101011, which is binary representation of 43 i.e. x2 become x1 = 43. The function value changes from f (x2) =0.7193 to f (x1) =0.6819. Clearly, the function value decreases so as the potential energy decreases or in other words the conceptual atom becomes more stable. But after the excitation from position x4 = 98 to x3 = 92 the function value changes from f (x4) =0.9903 to f (x3) =0.9994. Although in this case, the potential energy decreases but the function value increases which is a contradiction and it should not be happened. This situation is handled very nicely by the rehabilitation operator. When potential energy decreases and function value increases then the probability of de-excitation of electron bit increases. In rehabilitation operator E emit is inversely proportional to the function value and directly proportional to the potential. Therefore, the minimum requirement for de-excitation to any lower energy level decreases with the increment of fitness value and decrement of potential energy. Hence, divergence from the optima due to excitation operator is negotiated by the de-excitation operation. Rehabilitation operator also acts when both potential energy and function value decreases but in that case effectiveness of this operator is less, as the minimum requirement for de- excitation become comparatively higher. Hence, overall convergence towards the optima remains ineffective even though rehabilitation operator is applied in that case.
Another prime mechanism of alternation operator which stimulates atoms to occupy automatically the positions those are suitable for convergence. During alternation operation higher positive charged atoms attracted towards higher negative charged atoms. To characterize these attraction atoms are displaced on the basis of their potential energy and charge. Both low positively and negatively charged atoms are concentrated towards the mid position where as highly charged atoms concentrated towards the ends as shown in Fig. 6. This magnificent arrangement results in atoms to align (in case of n dimensional problems) with the same set of variables whose potential energies are comparatively lower or higher. Even more with this arrangement form bonds among those atoms to become more stable by exchanging of electron bits with each other. This kind of exchange actual takes place in the outer most shell or the 1st bit of atoms which implies that atoms having higher potential energy exploits around themselves, where as comparatively lower potential energy atoms are automatically debarred from this kind of exploitation. This implies that if an atom is nearby to the optima it hold on its position where as atom which are far from optima exploits for better state than current one. Clearly it seems that the alternation operator stimulates atoms to concentrate to their stable state with the notion of exploitation around the present states of atoms.
Experimental results
Most of the optimization algorithm uses random values during execution. Hence it is very difficult to prove whether an optimization algorithm is good or bad. However, convergence rate towards any optimal solution of any optimization problem and optimality of the solution is comparable. All optimization algorithm does not show good performance in every problem. Hence, performance should be compared on some standard problems. Six well known benchmark functions presented in Table 1 are considered for measuring performance of the proposed algorithm. Sphere and Zakharov functions are unimodal and remaining four functions are multimodal function.
Simulation strategy
Simulations have been carried out in MATLAB to observe the rate of convergence and the quality of the optimum solution of the new algorithm introduced. In this investigation both versions of ASA has been compared with GA, PSO-TVIW and jDE. All benchmark functions have been tested with dimensions 10, 20 and 30 for maximum generations up to 1000, 2000 and 3000 respectively. For each benchmark function, 50 trials have been carried out to measure quality of optimal solutions obtained. Two performance metrics mean and standard deviation have been considered for our analysis. Convergence is analyzed by plotting mean fitness corresponding obtained at each generation for all benchmark functions with 30 dimension up to 1000 generations.
Experimental setup
To examine performance of ASA, all experiments are carried out with population size 40. Crossover and mutation probability of GA are considered 0.8 and 0.35 respectively. Parameters of PSO-TVIW such as C1 set with value 0.5, C2 set with value 1.5 and ω gradually decreased from 0.9 to 0.4. Parameters of jDE are initialized with random values and adapted during execution. Parameters of ASA such as work function φ set with value 0.95, constant C set with value 0.85, probability of not to rehabilitate (NRh) set with value 0.25 and the probability of rehabilitation from outside the atom (E m ) set with value 0.15. For ASA-II, alternation probability A is set with value 0.15 and 25% of outermost shells to perform alternation.
Result analysis
Results obtained over 50 trials on each function are presented in Table 2. Clearly, performance of both versions of ASA outperforms GA, PSO-TVIW and jDE in most of the functions. ASA performance is best in Rastrigin, Ackely and Griwank function for all dimensions. In Sphere, Levy and Zakharov functions, ASA shows poor results for dimension 10. However, for dimensions 20 and 30, performance of ASA is better than GA, PSO-TVIW and jDE. Specially, for the Levy function also ASA performs better, where solution space is disturbed and optima not lies at center. Overall, both versions of ASA performs better than other three algorithms. ASA-II is more effective than ASA-I in generating good quality solutions.
Convergence rate of ASA-I, ASA-II and PSO-TVIW are presented in Fig. 7. Clearly, both ASA-I and ASA-II show high convergence rate in Rastrigin function than PSO-TVIW and reaches better solutions. In Griwank function, both ASA-I and ASA-II converge faster than PSO-TVIW. In Ackley function, ASA-I converges very fast whereas ASA-II converges at similar rate as ASA-I but does not converges at the end and continues exploring. On the other hand, PSO-TVIW converges slowly in comparison to both ASA-I and ASA-II. In Zakharov function, ASA-I converges fast but ASA-II converges slowly at the beginning and reaches optimal solution, while PSO-TVIW converges very slowly and unable to reach the optimal solution at the end. Overall, in most of the cases both ASA-I and ASA-II show high convergence rate than PSO-TVIW, particularly the Sphere and the Levy function.
Effectiveness of parameters
The proposed ASA algorithm has five parameters. These parameters give the flexibility and wide range of control over solution quality. For instance, the parameter C and φ are used to control excitation and escaping of bits for exploration. The parameter (NRh) is used to control de-excitation of bits and (E m ) for revoking bits to solutions that have less fitness value. Alternation probability A is used to control the percentage of outermost shells that undergo exchanging of bits. On the contrary, GA has two parameters crossover probability and mutation probability. Parameters of PSO-TVIW has four parameters C1, C2, ω, V max for controlling the quality of solutions. The jDE algorithm has three parameters F, CR and NP, these are initialized with random values and adapted during execution.
Real life applications
Performance of ASA has been tested above with benchmark functions. In this section, we discuss real life applications of ASA. First one is test case generation problem related to software testing. Second problem is the Royal Roads problem and lastly, the 01-Knapsack problem are discussed and compared performance of ASA with other algorithms. Implementation details of ASA to these problems are illustrated below.
Test case generation using ASA
Software testing is very important phase of software development life cycle. Main objective of software testing is to improve confidence level that the software will work as per user requirement. Numerous software testing techniques are exercised for the enrichment of software quality. Software testing techniques can be broadly categorized into Black Box testing and White Box testing. Black Box testing examines functionality of software without looking into the internal structure. On the contrary, White Box testing examines structure of software. Test case generation is an intermediate phase of White Box testing. Test cases are generated for maximum statement coverage, branch coverage and path coverage. We consider test case generation for branch coverage.
Objective of test cases for branch coverage is to maximize the ability of test cases to check branches. Aim is to find such set of test cases which cover maximum branches in the software, which is nothing but an optimization problem. To achieve test cases that fulfill this coverage criterion requires to search in the input domain. This becomes very tedious task specially when input domain is large. Automatic test case generation will be helpful for larger input domains. Though, test case generation process has been automated with optimization techniques [24, 28], still require more efficient approach that can reduce overall production cost. Implication of ASA into test case generation process is illustrated as follows: ASA is initialized with random input values from the respective ranges of input variables of test case generation process. These input variables are simply the inputs to the software. Input variables and with their ranges constitute input domain or search space for ASA. ASA optimizes the input values and gives partial output. These partial outputs are improved test cases. Improvement in the test cases is evaluated in terms of pre-specified objective function. We consider maximization of branch coverage as an objective function. Branch coverage of test cases are measured with Gcov
1
tool. It gives percentage of branches covered out-of total branches present in the software. Criterion for stopping the process are pre-specified maximum coverage with respect to software and maximum generations required. The process will continue until one of the criterion exhausts.
To evaluate performance of ASA in generating test cases, we have considered four programs asfollows:
We have compared performance of ASA with GA, PSO-TVIW and jDE. Each algorithm is tested on four programs 15 times. We have noted maximum coverage achieved and average number of generations needed. Performances are presented in Fig. 8. Result indicates test cases generated with ASA have highest ability to cover branches and also require least number of generations to achieve maximum coverage.
Royal Roads problem
The Royal Road functions are special class of fitness landscapes developed by Mitchell and his colleagues [30]. A Royal Road function consists of a list of partially specified bit strings called schema. Any schema s
i
contains two types of positions: specified position and unspecified position. Specified positions are strictly supposed to be either 1 or 0, which not allows 0 if it is specified as 1 and vice-versa. On the contrary, unspecified positions ‘*’ are like wild cards where both 0 and 1 are allowed. Order of a schema is denoted by the number of specified bits in the schema. A bit string x is referred as an instance of a schema s
i
, x ∈ s
i
, if x has matches in the specified (i.e., non-‘*’) positions of s
i
. The Royal Road function f (x) of a bit string x used for the experiments is defined as follows:
Performance of ASA is evaluated on the above defined Royal Roads problem and compared with GA, PSO-TVIW and jDE. Each algorithm is executed with population size of 120 for 200 generations. Results obtained for 50 trials are presented in the Table 3. Clearly, ASA performs better than all the three algorithms. The ASA attains better average optimal values for the same numbers of generations.
01-Knapsack problem
The knapsack problem is a combinatorial optimization problem. Given a set of items, each with a weight and a profit and the objective is to determine the number of each item to include in a collection so that it represents the maximum total profit, provided total weight is less than or equal to a given capacity. The 01-Knapsack problem restricts the number of each kind of items to zero or one. Thus, 01-Knapsack problem with a set of n items numbered from 1 up to n, each having a weight w
i
and a profit p
i
, along with a maximum weight capacity C is defined as follows:
Here, x is the bit string of 1s and 0s, x i represents absence or presence of any item in the Knapsack.
For the experimentation, first six instances of KNAPSACK01 data set 2 are considered. Each of the instances from P01 to P06 avails data for 01-Knapsack problem that are summarized in the Table 4. Performance of ASA is evaluated on the all six instances and compared with GA, PSO-TVIW and jDE. Each algorithm is executed with population size of 30 for 200 generations. Results obtained for 50 trials are presented in the Table 5. ASA performs better in almost all of the six 01-Knapsack data. Performance of GA is worst in all of the 01-Knapsack data. Success rate of ASA-I noted is 100% in all of the six 01-Knapsack data except P03. However, ASA-I requires comparatively less numbers of generation to attain optimal selection on P03. On the other hand, ASA-II requires very less numbers of generations to acquire optimal selections in comparison to GA, PSO-TVIW and jDE. Success rate of ASA-II is noted 100% in all of the six 01-Knapsack data.
Conclusion
An algorithm called Atom Stabilization Algorithm (ASA) has been introduced in this paper for solving optimization problems. The algorithm is designed based on atomic model. Solutions of search domain are represented as atoms by placing binary encoded bits into various shells of atom inferring those as electron bits to the atom. Excitation, de-excitation and bond formation mechanism enriched proposed algorithm with immense exploration of search domain. Two versions of ASA has been proposed ASA-I and ASA-II. In ASA-I, alternation operator is absent, whereas in ASA-II alternation operator is applied with smaller probability. Performance is measured on six well known benchmark functions and compared with GA, PSO-TVIW and jDE. ASA performs better than all of the three algorithms in terms of solution quality. Convergence rate of ASA is also quite high. ASA-I shows high convergence rate and reach optimal solution quickly. ASA-II shows high exploiting ability and reaches comparatively better optimal solution. At present, the algorithm is applicable to both continuous optimization and combinatorial optimization problem. In future work, the algorithm will be modified to suit in the case of multi-objective problems.
Performance of ASA is also evaluated on real life problems such as test case generation problem of software testing, the Royal Roads problem and the 01-Knapsack problem. Test cases generated with ASA are better in terms of maximum branch coverage than GA, PSO-TVIW and jDE. In the Royal Roads problem, ASA attains better average optimal values than GA, PSO-TVIW and jDE for the same numbers of generations. In the 01-Knapsack problem also requires very less numbers of generations to acquire optimal selection on almost all of the six 01-Knapsack data. Moreover, success rate of ASA is also noted higher than GA, PSO-TVIW and jDE. Overall, ASA is comparatively very efficient in terms of time required to reach good quality solutions.
