PaperlayerView exact revision on arXiv

Source-linked AI summary

Memetic firefly algorithm for combinatorial optimization

Iztok Fister Jr, Xin-She Yang, Iztok Fister, Janez Brest

arXiv:1204.5165v2math.OCmath.GR

TL;DR

The paper examines firefly algorithms for combinatorial optimization using graph 3-coloring. It evaluates a memetic firefly algorithm and reports better results than HEA and Tabucol on uniform and equi-partite graphs, but slightly worse results on flat graphs.

  • Problem

    The paper considers applying firefly algorithms to combinatorial optimization, using the NP-complete graph 3-coloring problem as a test case.

    Source: §I · p. 2

  • Method

    The paper evaluates a proposed memetic firefly algorithm (MFFA) for graph 3-coloring.

    Source: §I · pp. 2–3

  • Results

    MFFA produced better results than HEA and Tabucol on medium-scale uniform and equi-partite graphs, but was slightly worse on flat graphs, hardest for all tested algorithms.

    Source: §V · p. 11

  • Takeaways & Limitations

    The results suggest MFFA could be a promising tool for 3-GCP and potentially other combinatorial optimization problems.

    Source: §V · p. 11

    Results of other parameter-tuning experiments were omitted.

    Source: C. Discussion · p. 11

Abstract

from arXiv · show

Firefly algorithms belong to modern meta-heuristic algorithms inspired by nature that can be successfully applied to continuous optimization problems. In this paper, we have been applied the firefly algorithm, hybridized with local search heuristic, to combinatorial optimization problems, where we use graph 3-coloring problems as test benchmarks. The results of the proposed memetic firefly algorithm (MFFA) were compared with the results of the Hybrid Evolutionary Algorithm (HEA), Tabucol, and the evolutionary algorithm with SAW method (EA-SAW) by coloring the suite of medium-scaled random graphs (graphs with 500 vertices) generated using the Culberson random graph generator. The results of firefly algorithm were very promising and showed a potential that this algorithm could successfully be applied in near future to the other combinatorial optimization problems as well.

I. INTRODUCTION

The paper addresses the limited use of firefly algorithms in combinatorial optimization by applying a memetic firefly algorithm (MFFA) to graph 3-coloring. Its reported comparisons find MFFA comparable to or better than the tested algorithms.

I. INTRODUCTION

  • The paper applies firefly optimization to graph 3-coloring to investigate its use in combinatorial optimization, where relatively few applications had been published.The introduction contrasts this with firefly algorithms' promising results on continuous optimization problems.Source: §I · p. 2
  • MFFA represents solutions as real-valued vertex weights, sorts vertices by weight, constructs colorings with DSatur, and incorporates swap local search and elitism.Higher weights indicate vertices that should be colored sooner.Source: §I · p. 3
  • The experiments compare MFFA with EA-SAW, Tabucol, and HEA on medium-scale random graphs generated by the Culberson graph generator.The introduction identifies the compared algorithms and benchmark source.Source: §I · p. 3
  • MFFA produced results comparable to or better than the other algorithms used in the experiments.The comparison covered EA-SAW, Tabucol, and HEA on random medium-scale graphs.Source: §I · p. 3

II. GRAPH 3-COLORING

The section formulates graph 3-coloring as assigning one of three colors to every vertex so adjacent vertices differ. It also describes constraint penalties that score improper colorings.

II. GRAPH 3-COLORING

  • The section defines the graph as an undirected graph with vertices V and edges E connecting vertex pairs.Each edge constraint is satisfied exactly when its endpoint vertices have different colors.Source: §II · p. 4
  • Graph 3-coloring assigns each vertex one of three colors, with different colors required at the endpoints of every edge.The section represents the problem as a constraint satisfaction problem with a search space and feasibility condition.Source: §II · p. 4
  • The penalty function punishes unfeasible colorings more when they are farther from the feasible region, and Eq. (1) also serves as the objective function.A value of zero corresponds to a proper coloring.Source: §II · pp. 4–5

III. MEMETIC FIREFLY ALGORITHM FOR GRAPH 3-COLORING

The memetic firefly algorithm (MFFA) adapts firefly search to graph 3-coloring by representing candidate solutions as real-valued vertex weights and decoding their order with DSatur. The search evaluates colorings and moves fireflies toward more attractive solutions, with termination upon reaching the evaluation limit or finding a proper coloring.

III. MEMETIC FIREFLY ALGORITHM FOR GRAPH 3-COLORING

  • MFFA combines firefly search with a local search heuristic for graph 3-coloring.The method represents each candidate as a real-valued vector of weights assigned to vertices; sorting the weights yields a vertex permutation decoded by DSatur.Source: §III · pp. 5–6
  • Each iteration evaluates solutions, orders the population, records the best solution, and moves fireflies toward more attractive neighbors.Evaluation converts weights to a vertex permutation and uses DSatur to produce a coloring, whose quality is assessed in the original problem space.Source: §III · pp. 5–6
  • The search stops when objective-function evaluations reach MAX FES or a proper coloring is found.The population is initialized randomly within the specified weight bounds.Source: §III · p. 6
  • A firefly moves under the influence of every brighter firefly, combining an attractiveness-based movement with a randomized search-space move.Attractiveness depends on distance, the attractiveness at zero distance, and the absorption coefficient.Source: §III · p. 7

A. The heuristical swap local search

The heuristical swap operator moves the first uncolored vertex behind a predecessor with the highest saturation degree, using a random choice to break ties. The local search repeats this swap while it detects improvements.

A. The heuristical swap local search

IV. RESULTS

The experiments compare MFFA with EA-SAW, HEA, and Tabucol on 3-GCP using success rate and evaluations to solution. The study is preliminary, and it examines edge-density effects rather than time complexity or broader parameter dependence.

IV. RESULTS

  • The comparison tests MFFA against EA-SAW, HEA, and Tabucol, using success rate (SR) and average evaluations to solution (AES).SR is the ratio of successful runs to all runs; AES measures algorithm efficiency.Source: §IV · p. 8
  • Each algorithm runs each graph instance 25 times, with a maximum of 300,000 objective-function evaluations.MFFA uses a population size of 500.Source: §IV · p. 8
  • MFFA’s algorithm parameters were set to α = 0.1, β0 = 0.1, and γ = 0.8; these values optimize MFFA performance and were obtained through parameter tuning in extensive experimental work.Source: §IV · p. 8
  • The experiments aim to establish whether MFFA can be applied to 3-GCP; they omit time-complexity comparisons.Source: §IV · p. 8

A. Test-suite

The test suite uses Culberson-generated random graphs with 500 vertices across uniform, equi-partite, and flat types. Edge probabilities span the 3-coloring phase-transition region, producing 630 instances.

A. Test-suite

  • The suite uses Culberson-generated graphs, distinguished by type, vertex count, edge probability, and random-number seed.Source: A. Test-suite · p. 9
  • The experiments cover uniform, equi-partite, and flat graphs, with edge probability p from 0.008 to 0.028 in steps of 0.001.Source: A. Test-suite · p. 9
  • Ten seeds across 21 edge probabilities and three graph types yield 630 graphs, and each algorithm is run 15,750 times.Source: A. Test-suite · p. 9
  • The setup captures the 3-coloring phase transition, described as the region where an NP-hard problem shifts between solvability and unsolvability.The cited estimates place the transition near p = 0.016, with Eiben et al.'s interval given as 0.014 ≤ p ≤ 0.016.Source: A. Test-suite · p. 9

B. Influence of the edge density

MFFA outperforms HEA and Tabucol on uniform and equi-partite graphs, but is slightly worse on flat graphs; EA-SAW trails the other algorithms across graph types. The figure compares success rate and evaluations to solution, with outcomes also varying around the phase transition.

B. Influence of the edge density

C. Discussion

The discussion identifies search-design choices that improved MFFA and explains how local search and elitism shape exploration. It also notes limits in parameter tuning and describes the results as preliminary.

C. Discussion

  • Other parameter-tuning experiments were omitted because of limited paper length.Source: C. Discussion · p. 11
  • Using P(t) rather than intermediate population P′ for movement added randomness to the search and significantly improved results.The discussion contrasts calculating the movement from the population P(t) with calculating it from P′.Source: C. Discussion · p. 11
  • The best solution directs exploration toward more promising regions, so the discussion says it needs to be preserved.Source: C. Discussion · p. 11
  • Local search explores basins of attraction in detail, allowing discovery of solutions the regular FFA search would normally ignore.Source: C. Discussion · p. 11
  • Tests of self-adapting α produced no improvement, although α sets the size of the randomness move within the search space.Source: C. Discussion · p. 11
  • The authors characterize the MFFA results as preliminary and say they encourage further development.Source: C. Discussion · p. 11

V. CONCLUSION

MFFA performed better than HEA and Tabucol on medium-scale uniform and equi-partite graphs, but was slightly worse on flat graphs, which remained hardest for the tested algorithms. The authors caution that large-scale tests are needed before drawing firm conclusions.

V. CONCLUSION

  • The authors describe MFFA as a promising potential tool for 3-GCP and, consequently, other combinatorial optimization problems.Source: §V · p. 11
  • MFFA produced better results than HEA and Tabucol on medium-scale uniform and equi-partite graphs, but was slightly worse on flat graphs, the hardest for all tested algorithms.Source: §V · p. 11
  • The authors caution that the results could be misleading until experiments on graphs with 1,000 vertices are performed.Source: §V · pp. 11–12
  • The authors identify several possible ways to improve MFFA in the future.Source: §V · p. 12
Loading 1204.5165v2…