Narrow Results

One of the most essential operations in biological sequence analysis is multiple sequence alignment (MSA), where it is used for constructing evolutionary trees for DNA sequences and for analyzing the protein structures to help design new proteins. In this research study, a new method for solving sequence alignment problem is proposed, which is named improved tabu search (ITS). This algorithm is based on the classical tabu search (TS) optimizing technique. ITS is implemented in order to obtain results of multiple sequence alignment. Several variants concerning neighborhood generation and intensification/diversification strategies for our proposed ITS are investigated. Simulation results on a large scale of datasets have shown the efficacy of the developed approach and its capacity to achieve good quality solutions in terms of scores comparing to those given by other existing methods.

This paper introduces a Multi-Agent based Optimization Method for Combinatorial Optimization Problems named MAOM-COP. In this method, a set of agents are cooperatively interacting to select the appropriate operators of metaheuristics using learning techniques. MAOM-COP is a flexible architecture, whose objective is to produce more generally applicable search methodologies. In this paper, the MAOM-COP explores genetic algorithm and local search metaheuristics. Using these metaheuristics, the decision-maker agent, the intensification agents and the diversification agents are seeking to improve the search. The diversification agents can be divided into the perturbation agent and the crossover agents. The decision-maker agent decides dynamically which agent to activate between intensification agents and crossover agents within reinforcement learning. If the intensification agents are activated, they apply local search algorithms. During their searches, they can exchange information, as they can trigger the perturbation agent. If the crossover agents are activated, they perform recombination operations. We applied the MAOM-COP to the following problems: quadratic assignment, graph coloring, winner determination and multidimensional knapsack. MAOMCOP shows competitive performances compared with the approaches of the literature.