A Quantum-Inspired Evolutionary Computing Algorithm for Disk Allocation Method

SUMMARY Based on a Quantum-inspired Evolutionary Al- gorithm (QEA), a new disk allocation method is proposed for distributing buckets ofa binary cartesian product file among unrestricted number ofdisks to maximize concurrent disk I/O. It manages the probability distribution matrix to represent the qualities ofthe genes. Determining the excellent genes quickly makes the proposed method have faster convergence than DAGA. It gives better solutions and 3.2 - 11.3 times faster convergence somes). The population evolves by simple operations such as reproduction, crossover and mutation of the so- lutions (5). The excellent genes remain in the solutions selected based on the law of the survival of the fittest. The genetic algorithm is so general that it can be ap- plied to various problems. However, its converging time is too long due to the control based on the chromosomes not on the genes. In (6), Han and Kim proposed a Quantum-inspired Evolutionary Algorithm (QEA) whose convergence is faster than that of the conventional genetic algorithms. It is an evolutionary algorithm which is similar to the genetic algorithm. Its evolution status representation and evolution process are more efficient than those of the genetic algorithm. The evolution status of QEA is represented by a probability distribution matrix which represents the qualities of the genes. A population is sampled based on the probability distribution matrix and is evaluated. By using an insight to a given prob- lem, excellent genes are determined and their probabil- ities are increased, which makes the converging time of QEA faster than that of the genetic algorithms. In this paper, we propose QEA-based Disk alloca- tion Method (QDM) of buckets in a binary cartesian product file among multiple disks to minimize the av- erage response time of all the partial match queries on the file. QDM gives better solutions than DAGA and QDM is 3.2 - 11.3 times faster than DAGA for gener- ating the solutions of equal quality. 2. Problem Definition