Solving the Gale-Shapley Problem by Ant-Q Learning


The KIPS Transactions:PartB , Vol. 18, No. 3, pp. 165-172, Jun. 2011
10.3745/KIPSTB.2011.18.3.165,   PDF Download:

Abstract

In this paper, we propose Ant-Q learning Algorithm[1], which uses the habits of biological ants, to find a new way to solve Stable Marriage Problem(SMP)[3] presented by Gale-Shapley[2]. The issue of SMP is to find optimum matching for a stable marriage based on their preference lists (PL). The problem of Gale-Shapley algorithm is to get a stable matching for only male (or female). We propose other way to satisfy various requirements for SMP. ACS(Ant colony system) is an swarm intelligence method to find optimal solution by using phermone of ants. We try to improve ACS technique by adding Q learning[9] concept. This Ant-Q method can solve SMP problem for various requirements. The experiment results shows the proposed method is good for the problem.


Statistics
Show / Hide Statistics

Statistics (Cumulative Counts from September 1st, 2017)
Multiple requests among the same browser session are counted as one view.
If you mouse over a chart, the values of data points will be shown.


Cite this article
[IEEE Style]
H. Kim and T. C. Chung, "Solving the Gale-Shapley Problem by Ant-Q Learning," The KIPS Transactions:PartB , vol. 18, no. 3, pp. 165-172, 2011. DOI: 10.3745/KIPSTB.2011.18.3.165.

[ACM Style]
Hyun Kim and Tae Choong Chung. 2011. Solving the Gale-Shapley Problem by Ant-Q Learning. The KIPS Transactions:PartB , 18, 3, (2011), 165-172. DOI: 10.3745/KIPSTB.2011.18.3.165.