Modification of the Ant Colony Optimization Algorithm for Solving the Matching Problem with Vanishing Arcs

Authors

DOI:

https://doi.org/10.20535/1810-0546.2017.2.96638

Keywords:

Matchings, Dicotyledonous graph, Ant colony optimization algorithm

Abstract

Background. The applied problem of making out the optimal schedule of reception of manipulation treatments can be reduced to the extended mathematical problem of search of maximal matchings in the dicotyledonous graph. The basic challenge of solving this problem is the necessity of taking into account the limits on the acceptance of procedures.

Objective. The aim of the paper is modification of the ant colony algorithm for solution of the problem of matching with the vanishing arcs.

Methods. The initial population forming method and modified method of analysis of way of ants are proposed.

Results. The carried out studies proved the possibility of receipt of feasible optimal solution of the problem of matching with the vanishing arcs at the use of the modified ant colony algorithm.

Conclusions. The proposed method can be used for development and application of the scheduling systems and operative management in a direct care as well as at the development of control systems by flexible CASS for enterprises with discrete type of production.

Author Biographies

Anna O. Danylchenko, Zhytomyr State Technological University

Department of computer engineering, senior teacher

Svetlana N. Kravchenko, Zhytomyr State Technological University

Department of Software Systems, senior teacher

References

A. Danilchenko et al., “Solving a class of problems scheduling genetic algorithms to cluster systems”, Vіsnik ZhІTІ, no. 4, pp. 130–135, 2004 (in Ukrainian).

A. Danilchenko and O. Danilchenko, Data Mining. Zhytomyr, Ukraine: ZhІTІ, 2009 (in Ukrainian).

E. Reinhold et al., Combinatorial Algorithms. Theory and Practice. Мoscow, SU: Mir, 1980 (in Russian).

А. Panіshev et al., “The problem of matching with the “disappearing” arcs”, Modelyuvannya ta Іnformatsіynі Tekhnologії, no. 63, pp. 75–81, 2012 (in Ukrainian).

С. Shtovba, “Ant algorithms. Exponenta Pro”, Matematika v Prilozhenijah, no. 4, pp. 70–75, 2003 (in Russian).

M. Dorigo et al., “Ant system: Optimization by a colony of cooperating agents”, IEEE Trans. Sys. Man Cybern. B, Cybern., vol. 26, no. 1, pp. 29–41, 1996. doi: 10.1109/3477.484436

J.D. Little et al., “The algorithm for solving the traveling salesman problem”, Jekonomika i Matematicheskie Metody, vol. 1, no. 1, pp. 90–107, 1965 (in Russian).

P. Biro et al., “Size versus stability in the marriage problem”, Theor. Comp. Sci., vol. 411, no. 16-18, pp. 1828–1841, 2010. doi: 10.1016/j.tcs.2010.02.003

M. Gelain et al., “Local search approaches in stable matching problems”, Algorithms, vol. 6, no. 4, pp. 591–617, 2013. doi: 10.3390/a6040591

W. Li et al., “A DNA Algorithm for the maximal matching problem”, Automation and Remote Control, vol. 76, no. 10, pp. 1797–1802, 2015. doi: 10.1134/s0005117915100070

Downloads

Published

2017-04-27

Issue

No. 2 (2017): Engineering

Section

Art

License

Copyright (c) 2017 NTUU KPI Authors who publish with this journal agree to the following terms:

    1. Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under CC BY 4.0 that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.

    2. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.

    3. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work