Zastosowanie kwantowych algorytmów genetycznych do selekcji cech

Abstract

In the article a feature selection problem for k-NN classifier in image segmentation has been analyzed. Feature selection has been considered as a two criteria combinatorial optimization problem. An objective of optimization process was to find a feature subset of image points, allowing good quality of segmentation in satisfactory time. A fitness function for feature subsets has been proposed, taking into account time needed for calculation of feature values and quality of segmentation. Three population-based heuristic methods of optimization have been compared: simple genetic algorithm and its two modifications, inspired by principles of quantum computing: QiGA (Quantum-Inspired Genetic Algorithm) and GAQPR (Genetic Algorithm with Quantum Probability Representation). Results of experiments with artificial and tomography textures have been presented. Przedmiotem artykułu jest zagadnienie selekcji cech, używanych przez klasyfikator minimalnoodległościowy k-NN w procesie segmentacji obrazów. Selekcja cech została potraktowana jako problem dwukryterialnej optymalizacji kombinatorycznej, której celem jest znalezienie takiego podzbioru cech punktów obrazu, który pozwala na zadowalającą segmentację w możliwie krótkim czasie. Zaproponowano funkcję oceny jakości podzbiorów cech, uwzględniającą dwa kryteria: czas potrzebny na obliczenie wartości cech oraz uzyskiwaną jakość segmentacji. W artykule porównano trzy populacyjne metody heurystyczne: klasyczny algorytm genetyczny oraz jego dwie modyfikacje, czerpiące inspirację z systemów informatyki kwantowej: QiGA (Quantum-Inspired Genetic Algorithm) oraz GAQPR (Genetic Algorithm with Quantum Probability Representation). W artykule przedstawiono wyniki otrzymane dla segmentacji tekstury sztucznej oraz tekstury tomograficznej.