Genetic local search for multicast routing with pre-processing by logarithmic simulated annealing

Article

Zahrani, M., Loomes, M., Malcolm, J., Ullah, A., Steinhoefel, K. and Albrecht, A. 2008. Genetic local search for multicast routing with pre-processing by logarithmic simulated annealing. Computers and Operations Research. 35 (6), pp. 2049-2070. https://doi.org/10.1016/j.cor.2006.10.001
TypeArticle
TitleGenetic local search for multicast routing with pre-processing by logarithmic simulated annealing
AuthorsZahrani, M., Loomes, M., Malcolm, J., Ullah, A., Steinhoefel, K. and Albrecht, A.
Abstract

Over the past few years, several local search algorithms have been proposed for various problems related to multicast routing in the off-line mode. We describe a population-based search algorithm for cost minimisation of multicast routing. The algorithm utilises the partially mixed crossover operation (PMX) under the elitist model: for each element of the current population, the local
search is based upon the results of a landscape analysis that is executed only once in a pre-processing step; the best solution found so far is always part of the population. The aim of the landscape analysis is to estimate the depth of the deepest local minima in the
landscape generated by the routing tasks and the objective function. The analysis employs simulated annealing with a logarithmic cooling schedule (logarithmic simulated annealing—LSA). The local search then performs alternating sequences of descending and ascending steps for each individual of the population, where the length of a sequence with uniform direction is controlled by
the estimated value of the maximum depth of local minima. We present results from computational experiments on three different routing tasks, and we provide experimental evidence that our genetic local search procedure that combines LSA and PMX performs better than algorithms using either LSA or PMX only.

Research GroupSensoLab group
PublisherPergamon
JournalComputers and Operations Research
ISSN0305-0548
Publication dates
PrintJun 2008
Publication process dates
Deposited17 Oct 2008
Output statusPublished
Digital Object Identifier (DOI)https://doi.org/10.1016/j.cor.2006.10.001
LanguageEnglish
File
Permalink -

https://repository.mdx.ac.uk/item/80v5q

Log in to edit

Download files

  • 33
    total views
  • 8
    total downloads
  • 1
    views this month
  • 0
    downloads this month

Export as

Related outputs

Long non-coding RNA structure and function: Is there a link? [Corrigendum]
Zampetaki, A., Albrecht, A. and Steinhofel, K. 2019. Long non-coding RNA structure and function: Is there a link? [Corrigendum]. Frontiers in Physiology, Frontiers Research Foundation. https://doi.org/10.3389/fphys.2019.01127
Long non-coding RNA structure and function: Is there a link?
Zampetaki, A., Albrecht, A. and Steinhofel, K. 2018. Long non-coding RNA structure and function: Is there a link? Frontiers in Physiology. 9. https://doi.org/10.3389/fphys.2018.01201
Crispr/Cas9 gene editing reveals novel tertiary constraints in clustered miRNA processing
Lataniotis, L., Albrecht, A., Kok, F., Monfries, C., Benedetti, L., Lawson, N., Hughes, S., Steinhofel, K., Mayr, M. and Zampetaki, A. 2018. Crispr/Cas9 gene editing reveals novel tertiary constraints in clustered miRNA processing. Cardiovascular Research. 114 (Supp_1), pp. S1-S1. https://doi.org/10.1093/cvr/cvy060
Crispr/Cas9 gene editing reveals novel tertiary constraints in clustered mirna processing
Lataniotis, L., Albrecht, A., Kok, F., Monfries, C., Benedetti, L., Lawson, N., Hughes, S., Steinhofel, K., Mayr, M. and Zampetaki, A. 2017. Crispr/Cas9 gene editing reveals novel tertiary constraints in clustered mirna processing. Heart. 103 (5), p. A133. https://doi.org/10.1136/heartjnl-2017-311726.193
Crispr/Cas9 editing reveals novel mechanisms of clustered microRNA regulation and function
Lataniotis, L., Albrecht, A., Kok, F., Monfries, C., Benedetti, L., Lawson, N., Hughes, S., Steinhofel, K., Mayr, M. and Zampetaki, A. 2017. Crispr/Cas9 editing reveals novel mechanisms of clustered microRNA regulation and function. Scientific Reports. 7, pp. 1-14. https://doi.org/10.1038/s41598-017-09268-0
Random versus deterministic descent in RNA energy landscape analysis
Day, L., Souki, O., Albrecht, A. and Steinhofel, K. 2016. Random versus deterministic descent in RNA energy landscape analysis. Advances in Bioinformatics. 2016. https://doi.org/10.1155/2016/9654921
A new heuristic method for approximating the number of local minima in partial RNA energy landscapes
Albrecht, A., Day, L., Souki, O. and Steinhofel, K. 2016. A new heuristic method for approximating the number of local minima in partial RNA energy landscapes. Computational Biology and Chemistry. 60, pp. 43-52. https://doi.org/10.1016/j.compbiolchem.2015.11.002
iRDA: a new filter towards predictive, stable, and enriched candidate genes
Lai, H., Albrecht, A. and Steinhofel, K. 2015. iRDA: a new filter towards predictive, stable, and enriched candidate genes. BMC Genomics. 16. https://doi.org/10.1186/s12864-015-2129-5
Robust signature discovery for affymetrix GeneChip® cancer classification
Lai, H., Albrecht, A. and Steinhofel, K. 2015. Robust signature discovery for affymetrix GeneChip® cancer classification. 6th International Conference on Agents and Artificial Intelligence. Angers, France 06 - 08 Mar 2014 Springer. pp. 329-345 https://doi.org/10.1007/978-3-319-25210-0_20
A new vision of evaluating gene expression signatures
Lai, H., Otzturk, C., Albrecht, A. and Steinhofel, K. 2015. A new vision of evaluating gene expression signatures. Computational Biology and Chemistry. 57, pp. 54-60. https://doi.org/10.1016/j.compbiolchem.2015.02.004
MicroRNA target prediction based upon metastable RNA secondary structures
Souki, O., Day, L., Albrecht, A. and Steinhofel, K. 2015. MicroRNA target prediction based upon metastable RNA secondary structures. 3rd International Work-Conference on Bioinformatics and Biomedical Engineering (IWBBIO 2015). Granada, Spain 15 - 17 Apr 2015 Springer. pp. 456-467 https://doi.org/10.1007/978-3-319-16480-9_45
A framework for high-throughput gene signatures with microarray-based brain cancer gene expression profiling data
Lai, H., Albrecht, A. and Steinhöfel, K. 2014. A framework for high-throughput gene signatures with microarray-based brain cancer gene expression profiling data. 6th International Conference on Agents and Artificial Intelligence. Angers, France SCITEPRESS - Science and Technology Publications. https://doi.org/10.5220/0004926002110220
Energy-efficient multicast routing by using genetic local search
Katerinchuk, V., Albrecht, A. and Steinhofel, K. 2014. Energy-efficient multicast routing by using genetic local search. 6th International Conference on Agents and Artificial Intelligence. Angers, France 06 - 08 Mar 2014 pp. 740-746
Accessibility of microRNA binding sites in meta-stable RNA secondary structures in the presence of SNPs
Day, L., Abdelhadi Ep Souki, O., Albrecht, A. and Steinhofel, K. 2014. Accessibility of microRNA binding sites in meta-stable RNA secondary structures in the presence of SNPs. Bioinformatics. 30 (3), pp. 343-352. https://doi.org/10.1093/bioinformatics/btt695
A firefly-inspired method for protein structure prediction in lattice models
Maher, B., Albrecht, A., Loomes, M., Yang, X. and Steinhofel, K. 2014. A firefly-inspired method for protein structure prediction in lattice models. Biomolecules. 4 (1), pp. 56-75. https://doi.org/10.3390/biom4010056
Optimal placements of flexible objects. I. Analytical results for the unbounded case
Albrecht, A., Cheung, S., Hui, K., Leung, K. and Wong, C. 1997. Optimal placements of flexible objects. I. Analytical results for the unbounded case. IEEE Transactions on Computers. 46 (8), pp. 890-904. https://doi.org/10.1109/12.609278
Optimal placements of flexible objects. II. A simulated annealing approach for the bounded case
Albrecht, A., Cheung, S., Hui, K., Leung, K. and Wong, C. 1997. Optimal placements of flexible objects. II. A simulated annealing approach for the bounded case. IEEE Transactions on Computers. 46 (8), pp. 905-929. https://doi.org/10.1109/12.609279
The Steiner tree problem in orientation metrics
Yan, G., Albrecht, A., Young, G. and Wong, C. 1997. The Steiner tree problem in orientation metrics. Journal of Computer and System Sciences. 55 (3), pp. 529-546. https://doi.org/10.1006/jcss.1997.1513
Stochastic simulations of two-dimensional composite packings
Albrecht, A., Cheung, S., Leung, K. and Wong, C. 1997. Stochastic simulations of two-dimensional composite packings. Journal of Computational Physics. 136 (2), pp. 559-579. https://doi.org/10.1006/jcph.1997.5781
Computing elastic moduli of two-dimensional random networks of rigid and nonrigid bonds by simulated annealing
Albrecht, A., Cheung, S., Leung, K. and Wong, C. 1997. Computing elastic moduli of two-dimensional random networks of rigid and nonrigid bonds by simulated annealing. Mathematics and Computers in Simulation. 44 (2), pp. 187-215. https://doi.org/10.1016/S0378-4754(97)00072-4
Two simulated annealing-based heuristics for the job shop scheduling problem
Steinhofel, K., Albrecht, A. and Wong, C. 1999. Two simulated annealing-based heuristics for the job shop scheduling problem. European Journal of Operational Research. 118 (3), pp. 524-548. https://doi.org/10.1016/S0377-2217(98)00326-9
Logarithmic simulated annealing for X-ray diagnosis
Albrecht, A., Steinhofel, K., Taupitz, M. and Wong, C. 2001. Logarithmic simulated annealing for X-ray diagnosis. Artificial Intelligence in Medicine. 22 (3), pp. 249-260. https://doi.org/10.1016/S0933-3657(00)00112-3
Combining the perceptron algorithm with logarithmic simulated annealing
Albrecht, A. and Wong, C. 2001. Combining the perceptron algorithm with logarithmic simulated annealing. Neural Processing Letters. 14 (1), pp. 75-83. https://doi.org/10.1023/A:1011369322571
Fast parallel heuristics for the job shop scheduling problem
Steinhofel, K., Albrecht, A. and Wong, C. 2002. Fast parallel heuristics for the job shop scheduling problem. Computers and Operations Research. 29 (2), pp. 151-169. https://doi.org/10.1016/S0305-0548(00)00063-0
Bounded-depth threshold circuits for computer-assisted CT image classification
Albrecht, A., Hein, E., Steinhofel, K., Taupitz, M. and Wong, C. 2002. Bounded-depth threshold circuits for computer-assisted CT image classification. Artificial Intelligence in Medicine. 24 (2), pp. 179-192. https://doi.org/10.1016/S0933-3657(01)00101-4
The convergence of stochastic algorithms solving flow shop scheduling
Steinhofel, K., Albrecht, A. and Wong, C. 2002. The convergence of stochastic algorithms solving flow shop scheduling. Theoretical Computer Science. 285 (1), pp. 101-117. https://doi.org/10.1016/S0304-3975(01)00293-6
An experimental analysis of local minima to improve neighbourhood search
Steinhofel, K., Albrecht, A. and Wong, C. 2003. An experimental analysis of local minima to improve neighbourhood search. Computers and Operations Research. 30 (14), pp. 2157-2173. https://doi.org/10.1016/S0305-0548(02)00128-4
An Epicurean learning approach to gene-expression data classification
Albrecht, A., Vinterbo, S. and Ohno-Machado, L. 2003. An Epicurean learning approach to gene-expression data classification. Artificial Intelligence in Medicine. 28 (1), pp. 75-87. https://doi.org/10.1016/S0933-3657(03)00036-8
Classification improvement by an extended depth LSA machine
Albrecht, A. and Lappas, G. 2004. Classification improvement by an extended depth LSA machine. WSEAS Transactions on Systems. 3 (3), pp. 1120-1125.
On the evaluation of dividing samples for training an extended depth LSA machine
Albrecht, A. and Lappas, G. 2004. On the evaluation of dividing samples for training an extended depth LSA machine. WSEAS Transactions on Systems. 3 (3), pp. 1251-1257.
Gene selection guided by feature interdependence
Lai, H., Albrecht, A. and Steinhofel, K. 2013. Gene selection guided by feature interdependence. World Academy of Science, Engineering and Technology (WASET).
Derivative scores from site accessibility and ranking of miRNA target predictions
Dayem Ullah, A., Sahoo, S., Steinhofel, K. and Albrecht, A. 2012. Derivative scores from site accessibility and ranking of miRNA target predictions. International Journal of Bioinformatics Research and Applications. 8 (3/4), pp. 171-191. https://doi.org/10.1504/IJBRA.2012.048966
Ranking of microRNA target prediction scores by Pareto front analysis
Sahoo, S. and Albrecht, A. 2010. Ranking of microRNA target prediction scores by Pareto front analysis. Computational Biology and Chemistry. 34 (5-6), pp. 284-292. https://doi.org/10.1016/j.compbiolchem.2010.09.005
A note on a priori estimations of classification circuit complexity
Albrecht, A., Chashkin, A., Iliopoulos, C., Kasim-Zade, O., Lappas, G. and Steinhofel, K. 2010. A note on a priori estimations of classification circuit complexity. Fundamenta Informaticae. 104 (3), pp. 201-217. https://doi.org/10.3233/FI-2010-344
Uphill unfolding of native protein conformations in cubic lattices
Albrecht, A., Kapsokalivas, L. and Steinhofel, K. 2010. Uphill unfolding of native protein conformations in cubic lattices. Journal of Computational Science. 1 (1), pp. 6-12. https://doi.org/10.1016/j.jocs.2010.01.001
Analysis of local search landscapes for k-SAT instances
Albrecht, A., Lane, P. and Steinhofel, K. 2010. Analysis of local search landscapes for k-SAT instances. Mathematics in Computer Science. 3 (4), pp. 465-488. https://doi.org/10.1007/s11786-010-0040-7
Relating time complexity of protein folding simulation to approximations of folding time
Steinhofel, K., Skaliotis, A. and Albrecht, A. 2007. Relating time complexity of protein folding simulation to approximations of folding time. Computer Physics Communications. 176 (7), pp. 465-470. https://doi.org/10.1016/j.cpc.2006.12.002
Stochastic local search for the Feature Set problem, with applications to microarray data
Albrecht, A. 2006. Stochastic local search for the Feature Set problem, with applications to microarray data. Applied Mathematics and Computation. 183 (2), pp. 1148-1164. https://doi.org/10.1016/j.amc.2006.05.128
A stopping criterion for logarithmic simulated annealing
Albrecht, A. 2006. A stopping criterion for logarithmic simulated annealing. Computing. 78 (1), pp. 55-79. https://doi.org/10.1007/s00607-006-0167-1
A computational study on circuit size versus circuit depth
Lappas, G., Frank, R. and Albrecht, A. 2006. A computational study on circuit size versus circuit depth. International Journal on Artificial Intelligence Tools. 15 (2), pp. 143-162. https://doi.org/10.1142/S0218213006002606
Computer-assisted diagnosis of focal liver lesions on CT images: evaluation of the perceptron algorithm
Hein, E., Albrecht, A., Melzer, D., Steinhofel, K., Rogalla, P., Hamm, B. and Taupitz, M. 2005. Computer-assisted diagnosis of focal liver lesions on CT images: evaluation of the perceptron algorithm. Academic Radiology. 12 (9), pp. 1205 -1210. https://doi.org/10.1016/j.acra.2005.05.009
Stochastic protein folding simulation in the three-dimensional HP-model
Albrecht, A., Skaliotis, A. and Steinhöfel, K. 2008. Stochastic protein folding simulation in the three-dimensional HP-model. Computational Biology and Chemistry. 32 (4), pp. 248-255. https://doi.org/10.1016/j.compbiolchem.2008.03.004
Population-based local search for protein folding simulation in the MJ energy model and cubic lattices
Kapsokalivas, L., Gan, X., Albrecht, A. and Steinhöfel, K. 2009. Population-based local search for protein folding simulation in the MJ energy model and cubic lattices. Computational Biology and Chemistry. 33 (4), pp. 283-294. https://doi.org/10.1016/j.compbiolchem.2009.06.006
Combinatorial landscape analysis for k-SAT instances
Albrecht, A., Lane, P. and Steinhofel, K. 2008. Combinatorial landscape analysis for k-SAT instances. in: 2008 IEEE Congress on Evolutionary Computation (IEEE World Congress on Computational Intelligence) IEEE. pp. 2498-2504
Approximating the set of local minima in partial RNA folding landscapes
Sahoo, S. and Albrecht, A. 2012. Approximating the set of local minima in partial RNA folding landscapes. Bioinformatics. 28 (4), pp. 523-530. https://doi.org/10.1093/bioinformatics/btr715
A local search heuristic for bounded-degree minimum spanning trees
Zahrani, M., Loomes, M., Malcolm, J. and Albrecht, A. 2008. A local search heuristic for bounded-degree minimum spanning trees. Engineering Optimization. 40 (12), pp. 1115-1135. https://doi.org/10.1080/03052150802317440
Adaptive simulated annealing for CT image classification
Loomes, M., Albrecht, A., Steinhoefel, K. and Taupitz, M. 2002. Adaptive simulated annealing for CT image classification. International Journal of Pattern Recognition and Artificial Intelligence. 16 (5), pp. 573-588.
Landscape analysis for multicast routing
Loomes, M., Albrecht, A., Malcolm, J. and Zahrani, M. 2006. Landscape analysis for multicast routing. Computer Communications. 30 (1), pp. 101-116. https://doi.org/10.1016/j.comcom.2006.07.019