TITLE

Unified encoding for hyper-heuristics with application to bioinformatics

AUTHOR(S)
Swiercz, Aleksandra; Burke, Edmund; Cichenski, Mateusz; Pawlak, Grzegorz; Petrovic, Sanja; Zurkowski, Tomasz; Blazewicz, Jacek
PUB. DATE
September 2014
SOURCE
Central European Journal of Operations Research;Sep2014, Vol. 22 Issue 3, p567
SOURCE TYPE
Academic Journal
DOC. TYPE
Article
ABSTRACT
This paper introduces a new approach to applying hyper-heuristic algorithms to solve combinatorial problems with less effort, taking into account the modelling and algorithm construction process. We propose a unified encoding of a solution and a set of low level heuristics which are domain-independent and which change the solution itself. This approach enables us to address NP-hard problems and generate good approximate solutions in a reasonable time without a large amount of additional work required to tailor search methodologies for the problem in hand. In particular, we focused on solving DNA sequencing by hybrydization with errors, which is known to be strongly NP-hard. The approach was extensively tested by solving multiple instances of well-known combinatorial problems and compared with results generated by meta heuristics that have been tailored for specific problem domains.
ACCESSION #
97029513

 

Related Articles

  • Process plan and part routing optimization in a dynamic flexible job shop scheduling environment: an optimization via simulation approach. Geyik, Faruk; Dosdoğru, Ayşe Tuğba // Neural Computing & Applications;Nov2013, Vol. 23 Issue 6, p1631 

    This paper presents an optimization via simulation approach to solve dynamic flexible job shop scheduling problems. In most real-life problems, certain operation of a part can be processed on more than one machine, which makes the considered system (i.e., job shops) flexible. On one hand,...

  • AÇIK ATÖLYE TÄ°PÄ° ÇİZELGELEME PROBLEMLERÄ°NÄ°N PARALEL DOYUMSUZ METASEZGÄ°SEL ALGORÄ°TMA Ä°LE ÇÖZÃœMÃœ.  // e-Journal of New World Sciences Academy (NWSA);2011, Vol. 6 Issue 1, p421 

    No abstract available.

  • Performance Evaluation of Efficient Solutions for the QoS Unicast Routing. Bellabas, A.; Lahoud, S.; Molnár, M. // Journal of Networks;Jan2012, Vol. 7 Issue 1, p73 

    Quality of Service (QoS) routing known as multiconstrained routing is of crucial importance for the emerging network applications and has been attracting many research works. This NP-hard problem aims to compute paths that satisfy the QoS requirements based on multiple constraints such as the...

  • Project Scheduling Heuristics-Based Standard PSO for Task-Resource Assignment in Heterogeneous Grid. Ruey-Maw Chen; Chuin-Mu Wang // Abstract & Applied Analysis;2011, Special section p1 

    The task scheduling problem has been widely studied for assigning resources to tasks in heterogeneous grid environment. Effective task scheduling is an important issue for the performance of grid computing. Meanwhile, the task scheduling problem is an NP-complete problem. Hence, this...

  • Resource Sharing Models and Heuristic Load Balancing Methods for Grid Scheduling Problems. Wanneng Shu; Lixin Ding; Shenwen Wang // International Journal of Advancements in Computing Technology;May2012, Vol. 4 Issue 9, p315 

    Grid computing utilizes distributed heterogeneous resources to support large-scale or complicated computing tasks, and an appropriate resource scheduling algorithm is fundamentally important for the success of grid applications. Due to the complex and dynamic properties of grid environments,...

  • Solving Maximal Clique Problem through Genetic Algorithm. Rajawat, Shalini; Hemrajani, Naveen; Menghani, Ekta // AIP Conference Proceedings;11/6/2010, Vol. 1324 Issue 1, p235 

    Genetic algorithm is one of the most interesting heuristic search techniques. It depends basically on three operations; selection, crossover and mutation. The outcome of the three operations is a new population for the next generation. Repeating these operations until the termination condition...

  • LOCAL SEARCH IN ROUTING PROBLEMS WITH TIME WINDOWS. Savelsbergh, M. W. P. // Annals of Operations Research;1985, Vol. 4 Issue 1-4, p285 

    We develop local search algorithms for routing problems with time windows. The presented algorithms are based on the k-interchange concept. The presence of time windows introduces feasibility constraints, the checking of which normally requires O(N) time. Our method reduces this checking effort...

  • Efficient simulation of tissue-like P systems by transition cell-like P systems. Daniel Díaz-Pernil; Mario Pérez-Jiménez; Álvaro Romero-Jiménez // Natural Computing;Dec2009, Vol. 8 Issue 4, p797 

    Abstract  In the framework of P systems, it is known that the construction of exponential number of objects in polynomial time is not enough to efficiently solve NP-complete problems. Nonetheless, it could be sufficient to create an exponential number of membranes in polynomial time....

  • Complexity of evolution in maximum cooperative P systems. Gabriel Ciobanu; Andreas Resios // Natural Computing;Dec2009, Vol. 8 Issue 4, p807 

    Abstract  We introduce a variant of P systems called maximum cooperative P systems; it consists of transition P systems with cooperative rules that evolve at each step by consuming the maximum number of objects. The problem of distributing objects to rules in order to achieve a...

Share

Read the Article

Courtesy of THE LIBRARY OF VIRGINIA

Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics