A Swarm Intelligence Heuristic Approach to Longest Common Subsequence Problem for Arbitrary Number of Sequences
Ali Teoman Unay Meral Guzey · Journal of Postgenomics Drug & Biomarker Development · 2013
Particle swarm optimizationIn the field of computer science, PSO is a method that aims to optimize a problem by trying to improve a possible solution with iteration in limitation and manipulation of a pre-defined quality measure.PSO processes an initial population of possible solutions, dubbed particles in this case, and changing the position of these particles in the search-space according to mathematical formula which is consisting of the particles' (a) position and (b) velocity.An individual particle's movement is altered according to its "local best known position" and is also manipulated toward the "best known positions" in the search-space.The best known positions are updated as positions which are more satisfactory for quality criteria, are discovered by other particles.This mode of action is supposed to conduct the movement of the swarm toward the best solutions [5].PSO was first intended for simulating social behavior, as a stylized representation of the movement of organisms in a bird flock or fish school [6,7].The algorithm was simplified and it was observed to be performing optimization. Particle swarm optimization on longest common subsequence problemThis study uses PSO heuristic technique on LCSP.First, the algorithm will take n sequences and generate an alphabet among all of the distinct sequence elements without uncommon elements.Then it will generate a population of random sequences of the alphabet.Every sequence will be a particle.It will do the evaluation with the technique, occurrence evaluation, which will be described in detail in this paper.After the evaluation, known local best score will be compared with the global best score.If local best score is bigger, then it is the new global best (initial global best is 0).After this, each particle move towards to