Electimize

Electimize algorithms are a branch of evolutionary computation that simulate the phenomenon of electron flow and electrical conductivity. They have been designed to overcome the limitations of some non-linear optimization algorithms in measuring the effect of changing decision variable value on convergence potential. Electimize algorithms mimic electrons flow through electric circuit branches with low electric resistance to converge toward optimal solutions. In the developed approach, solutions are represented by electric wires which are evaluated on two levels: a global level using the objective function, and a local level that considers the potential of each generated value for every decision variable.

Background

Some evolutionary algorithms are limited in their capabilities of reaching optimal solutions, if they deal with candidate solutions indifferently and ignore the potential of each individual solution. In addition, most evolutionary algorithms strive to simulate change behavior without considering the impact of changes in the surrounding environment on the individuals simulated. Electimize was designed to overcome these limitations by providing capacity to evaluate the potential of each variable of a solution string, and adopting a natural phenomenon in which an individual tends to respond consistently.

The robustness of the algorithm is attributed to its multi-level evaluation process that enables assessing the potential of each generated value in the solution space.

Population

The population of Electimize algorithms is a collection of wires connected to an electric circuit. The wires are connected to parallel branches of the circuit.

Algorithm steps

The algorithm consists of nine basic steps:

1. Construction of wires (trial solutions): This step is accomplished by fabricating a number of wires (N), each composed of (M) segments of different material that are connected in series. Each segment is randomly assigned a value that is selected from the solution space. This value has a designated resistance value (rnm) in the solution space.
2. Construction of the electric circuit: Once all wires are fabricated, they are connected to an electric source of voltage (V).
3. Determining the electric current intensity (In): For each wire (Wn), the intensity of current (In) passing through it represents the value of the objective function for that wire solution.
4. Calculating the resistance of wires (Rn): The global resistance of each wire is calculated using Ohm's law: Rn = V/In.
5. Evaluating the quality of wires: The quality of a wire (Wn) is determined by its global resistance (Rn) and the wires are accordingly ranked with respect to one another. The worst wire (Ww) is then determined and used as a comparison medium to evaluate the quality of the generated wire segments.
6. Evaluating the quality of wire segments: The quality of each segment (m) in (Wn) is determined by calculating its local resistance (rnm). At first, it is assumed that all resistances (rnm) for segments (m:1 to M) are identical. In order to determine the actual resistance of each segment, a sensitivity analysis is conducted.
7. Updating resistances (rlm) for the generated values: At iteration(x=0), all the values in the solution space are considered to have the same quality as there is no prior information about their quality. Therefore, each value is assigned the same initial resistance (r0) that is determined by the algorithm. This is accomplished by dividing the global resistance (V/I) of the wire generated in step 2 by the number of segments. In each iteration (x), the resistance (rlm) is updated for each selected value (l) for each segment (m).
8. Selection of new values (lnm) for the variables: The selection process of new values is based on the individual resistance (rlm) associated with each value (l), which is updated after each iteration until the best wire is created.
9. Algorithm Termination: The algorithm terminates after the stipulated number of iterations is reached

Case studies

Some current research showed Electimize to be more efficient in solving NP-hard optimization problems than traditional evolutionary algorithms. The algorithm provides higher capacity in searching the solution space extensively, and identifying global optimal alternatives. Unlike other evolutionary algorithms, Electimize evaluates the quality of the values in the solution string independently.

Applications

• Various optimization problems
• Facility location problem
• Location-allocation

See also

• Artificial intelligence
• Artificial life
• Evolutionary computation
• Genetic algorithm
• Harmony search
• Machine learning
• Memetic algorithm
• Memetics
• Metaheuristic
• Social simulation
• Sociocultural evolution
• Stochastic optimization
• Swarm intelligence