Evolutionary computing (EC) techniques have been used traditionally used for solving challenging optimization problems. But the increase in data and information has reduced the performance capacity of the GA, but highlighted the cost of finding a solution by GA. In addition, the genetic algorithm employed in previous literature is modeled to solve one problem exactly. The GA needs to be redesigned, at a cost, for it to be applied to another problem. For these two reasons, this paper proposes a method for incorporating the GA and rough set theory. The superiority of the proposed GA in this paper lies in its ability to model problems and explore solutions generically. The advantages of the proposed solution approach include: (i) solving problems that can be decomposed into functional requirements, and (ii) improving the performance of the GA by reducing the domain range of the initial population and constrained crossover using rough set theory. The solution approach is exemplified by solving the problem of web services composition, where currently the general analysis and selection of services can be excessively complex and un-systemic. Based on our experimental results, this approach has shown great promise and operates effectively.
Evolutionary computing (EC) is the collective name for problem-solving techniques based on principles of biological evolution, such as natural selection and genetic inheritance (Eiben & Smith, 2007). Evolutionary computing techniques include genetic algorithms, particle swarm optimization and ants system (Kwok, Liu, & Dissanayake, 2006). Further, it has been used traditionally for solving challenging optimization problems (Eberbach, 2005), such as, optimization problems of searching (Bautista and Pereira, 2006, Bergey and Ragsdale, 2005 and Hwang and He, 2006), scheduling (Chang et al., 2007, Ruiz et al., 2006 and Yoo and Gen, 2007), production and distribution (Aliev et al., 2007, Chan et al., 2005 and Chen et al., 2008), knowledge discovery problems (Chen and Hsu, 2006 and Wachla and Moczulski, 2007), and machine learning (Chi et al., 2007 and Shon and Moon, 2007).
GA algorithms are efficient search methods based on the principles of natural selection and population genetics in which random operators in a population of candidate solutions are employed to generate new points in the search space (Chen & Hsu, 2006). But the increase in data and information has reduced the performance capacity of the GA, but highlighted the cost of finding a solution by using it. To solve the problem, Passone, Chung, and Nassehi (2006) combined the GA with the guidance provided by domain-specific knowledge. The GA consists of a modified version of the classical genetic operations of initialization, selection, crossover and mutation designed to incorporate practical but general principles of model without reference to any specific problems. The incorporated knowledge helps the GA to improve performance and quickly converge without affecting the result.
In this paper, the rough set theory introduced by Pawlak as a mathematical method (Beaubouef and Lang, 1998 and Questier et al., 2002) is used to improve the GA performance. Rough set theory is a powerful mathematical tool for dealing with uncertainty of data. It relies only on the available data and attributes to work on the analysis of important features as well as generation of classification rules (Wang, 2005). To cope with the inconsistency, lower and upper approximations of decision classes are defined. In the rough set method, we can extract the minimal attribute sets without deterioration of quality of approximation, and minimal length decision rules corresponding to lower or upper approximation (Inuiguchi & Miyajima, 2007). The applications of the rough set model in various problems have demonstrated its usefulness (Pattaraintakorn et al., 2006 and Zhao et al., 2007). It has been applied in many fields, such as pattern recognition (Wang et al., 2007a and Wang et al., 2007b), machine learning (Hu et al., 2008 and Wang, 2005), knowledge discovery (Li et al., 2007, Wang et al., 2007a and Wang et al., 2007b), decision analysis (Fan et al., 2007 and Inuiguchi and Miyajima, 2007), data mining (Li et al., 2007, Tsai et al., 2006 and Yang et al., 2007) and so on (Su and Hsu, 2006 and Zhu, 2007).
This study proposes a method for incorporating the GA and rough set theory. The superiority of the proposed GA in this paper lies in its ability to model problems and explore solutions generically. A problem can be solved if it can be decomposed into functional requirements which can be satisfied by the associated databases of basic units. However, more data in each database makes the GA less efficient. To solve this problem, the knowledge discovery approach, and in particular the rough set theory, is used to reduce the range of basic database units. The proposed GA incorporating the rough set theory can: (i) solve problems that can be decomposed into functional requirements, and (ii) improve the performance of the GA by reducing the domain range of the initial population and constrained crossover using rough set theory. Incorporating the RST rules improves GA performance.
This paper is organized as follows: In Section 2, the rough set theory and the literature review of web services composition is illustrated. Section 3 proposes a solution approach of generic genetic algorithm incorporating rough set theory. In Section 4, an illustrative example proves the superiority of the proposed approach. Section 5 concludes the paper.
In this paper, a novel approach has been proposed for a web services composition application, with a composition process that is systemic and completed. It shows great promise in the emerging demand for composite web services. Also, by proposing the rule generated by rough set which is applied to different GA parts, the constrained GA can operate effectively to thus promote the convergence and hit rate. The results show combining the constrained GA and rough set can provide better web services composition and let its convergence greatly improve. In future work, there are some other aspects to study. First, in rough set, we can use related tools to pick out the attributes to satisfy different requirements and find the key attributes to design the threshold to promote the accuracy of the rule. Second, users may not able to define the related parameters, so we can provide some parameter combinations for the users to refer to.
