International Journal of Innovative Computing and Applications (18 papers in press)
Improvement of the Greedy Algorithm for (n^2 1)-Puzzle
by Yuichi Asahiro, Kaede Utsunomiya
Abstract: The (n^2−1)-Puzzle is a generalization of the well known 15-Puzzle. Ratner and Warmuth (1990) showed that finding a shortest sequence of moves, for the (n^2−1)-Puzzle is NP-hard. Many researches have been devoted to the (n^2−1)-Puzzle so far. Also the (n2 − 1)-Puzzle is chosen as a benchmark problem in many researches developing a new method/strategy. For the (n2 − 1)-Puzzle, a real-time algorithm is proposed by Parberry (1995), which is based on a greedy method and completes the puzzle in at most 5n^3 − 9n^2/2 + O(n) moves and needs O(1) computation time per move, although there is no guarantee that the number of moves is optimal (shortest). Following the direction of the research by Parberry (1995), we present an algorithm, which is designed by modifying Parberrys algorithm and giving a tight analysis. The number of moves by the new algorithm is smaller, which needs at most 5n^3 − 11n^2 + O(n) moves, and computation time per move is also O(1).
Keywords: (n^2−1)-Puzzle; 15-Puzzle; greedy algorithm; theoretical analysis.
A novel artificial immune system based approach for mining associative classification rules with stock trading data
by Mahsa Mahboob Ghodsi, Mostafa Zandieh
Abstract: Stock market prediction with high accuracy has always been an interesting subject for most investors and professional analysts. Data mining techniques are providing great aid to extract interesting and hidden knowledge from datasets. Financial data mining tools assist investors in their investment decisions, thereby reducing their investment risks. Associative classification rule mining is a promising approach in data mining that utilizes the association rule discovery techniques to construct classification systems, also known as associative classifiers. This paper aims to develop an intelligent transaction system based on associative classification rule mining (ACR) and phenotypic artificial immune system (AIS) which discovers trading rules from numerical indicators. A new fitness function as a different measure of quality for quantitative association is suggested considering interestingness of rules. Based on the empirical studies on top 8 companies in the S&P 500 stocks, observed results demonstrate the superior prediction accuracy over the genetic algorithm based technique and the Buy and Hold strategy.
Keywords: Stock market prediction, Data mining techniques, Associative classification rule mining, Artificial immune system
Blind Users Assistive Technology Based on the Android Platform
by Jamal Al-Nabulsi, Jumana Ma’touq, Emad Eddien Abdallah
Abstract: Because of the wide use of smartphones in our daily activities, a wide range of mobile applications have been developed to serve as assistive technologies. However, there is a lack of applications in the Arabic language to assist disabled people. The main aim of this paper is to build a simple yet accurate Arabic language application that is capable of helping blind users in real-time. In the proposed technology, the blind user captures a photo and records his/her voice inquiry. The query is instantly sent with the captured photo to a set of volunteers. The volunteers answer the blind user enquiries and send the answers back. Fifteen visually impaired persons and 10 volunteers were used in the experimental testing. The scenarios were carefully created based on realistic situations. The subjects were then asked to answer a questionnaire to test if their queries were answered effectively and efficiently. The early results are promising because all blind users found the proposed technology useful and 80% of them wanted to use it on a daily basis. In addition, all volunteers found the application easy to use with clear instructions and 80% of them were excited about using it to assist blind users.
Keywords: blind user; mobile application; Arabic language; assistive technology; mobile phone
A clustering ensemble learning method based on the ant colony clustering algorithm
by Hamid Parvin
Abstract: Ensemble-based learning is a successful approach for robust partitioning. Since the ensemble classifiers cover each other fault, classification is a critical task. Generating a set of diverse basic partitions by a clustering algorithm with different initializations is the most common policy in clustering ensemble based learning. Then, within the selection phase, a subset of the generated partitions is chosen for the final ensemble. Therefore, a diverse ensemble is obtained. Ultimately, a final partitioning, called the consensus partitioning, is generated using a consensus function to aggregate the ensemble. Clustering ensemble based learning can also be done using fusion of some primary partitions which derive from naturally different sources. Another new topic is swarm intelligence where the simple agents act so that a complicated behaviour emerges. Inherent randomness of swarm intelligence algorithms results in the variety of ensembles. In this study, a novel clustering ensemble learning method inspired from the ant colony clustering algorithm is proposed. Since ensemble methods necessarily rely on diversity, swarm intelligence algorithms, such as ant colony, are can be good options to be applied. Executing this algorithm for several times on a dataset, result in various partitions. Then, a simple partitioning algorithm is exercised to aggregate them into a consensus partitioning. One important challenges of the ant colony algorithm has been its effectiveness due to its strong dependency to too many parameters. Hence, these parameters should be adjusted to achieve a satisfactory result on a dataset test. On the other hand, it is important to how to define them in an actual task. The proposed clustering approach lets the parameters be free to be manipulated, and thanks to the ensemble, non-optimality of the parameters is covered. Experimental results on several real datasets illustrate the efficiency of the proposed method to generate the final partitioning.
Keywords: Ant colony; ensemble classifiers; clustering; swarm intelligence; partitioning
A Quantum Encoding Bat Algorithm for Uninhabited Combat Aerial Vehicle Path Planning
by Yongquan Zhou
Abstract: Uninhabited combat aerial vehicle (UCAV) path planning aims to obtain an optimal or near-optimal flight path considering the different kinds of threats and constraints in the combat field. This paper a novel quantum encoding bat algorithm (QBA) for solving the path planning of UCAV is proposed. we using quantum rotation and quantum NOT gate are implemented to change the basic qubit states and to enhanced global search capability. The QBA can find a feasible and global path for the UCAV to avoid the threats and constrains. The experimental results show that the proposed QBA algorithm is an effective and feasible method in solving UCAV path planning problem than the some well-known algorithms.
Keywords: Bat algorithm; UCAV path planning; quantum enconding; quantum encoding bat algorithm.
Dual Neighborhood Discrete Artificial Bee Colony Algorithm for the Convex Polygons Packing Problem with Constraints of Equilibrium
by Zhendong Huang, Renbin Xiao
Abstract: For the optimal packing problem of convex polygons in a circular container with performance constraint, a hybrid algorithm which combines an improved ripple exploratory heuristic algorithm (IREHA) with dual-neighbourhood discrete artificial bee colony algorithm (DDABC) is proposed. IREHA improves search efficiency of the original REHA. Because of the excellent performance of artificial bee colony algorithm, which can not be directly used to optimize the discrete packing order, DDABC based on discrete dual neighbourhood structure is designed to combine with IREHA to form hybrid algorithm. The numerical experiments show that the hybrid algorithm is very effective.
Keywords: Equilibrium constraints; Packing optimization; Heuristic; Discrete artificial bee colony algorithm; Dual neighbourhood.
by Shashank Gupta, Brij Gupta
Evolutionary fuzzy rules for dynamic optimisation
by Khalid Jebari, Brahim Nasry, Abdelaziz Bouroumi, Aziz Ettouhami
Abstract: Dynamic optimisation problems (DOPs) have attracted a lot of studies from the genetic algorithms (GAs) community due to the importance in real-world applications. Many researchers have proposed algorithms to enhance the performance of GAs in DOPs. This paper proposes a number of remedies to improve the performance of GAs in DOPs. First, we use GAs with dynamic niche sharing (GADNS) to maintain diversity in the population and to find multiple optima. Second, an unsupervised fuzzy clustering algorithm is utilised to track multiple optima and to overcome some weaknesses of GADNS such as the use of fixed sharing outside the dynamic niches. Third, we use a fuzzy system to adjust the mutation and crossover rates, in order to diversify the population. A modified tournament selection is used to control the selection pressure. The effectiveness of our approach is demonstrated by using the generalised dynamic benchmark generator (GDBG) and the moving peaks benchmark.
Keywords: genetic algorithms; unsupervised learning; fuzzy clustering; dynamic optimisation; evolutionary algorithms; dynamic niche sharing; multimodal function optimisation; moving peaks benchmark; MPB; generalised dynamic benchmark generator; GDBG.
Case studies in divisive hierarchical clustering
by Paulo Rogério Nietto, Maria Do Carmo Nicoletti
Abstract: Hierarchical clustering algorithms can be characterised as agglomerative or divisive. Divisive clustering algorithms are not as popular as agglomerative, due to the complexity involved in their processes. The divisive algorithm DIvisive ANAlysis (DIANA) was proposed as an attempt to minimise the computational complexity embedded in divisive algorithms. This work focuses on an empirical comparative analysis of clustering results obtained by four algorithms, DIANA, k-means, EM and farthest first, in nine sets of patterns having different characteristics. Taking into account the sets of patterns used in the experiments, in general, the clusterings induced by the DIANA algorithm are an indication that the bisection strategy employed by the algorithm can produce clustering entirely different from those produced by the other three algorithms. Its splits are performed recursively down the clustering hierarchy, in a greedy way - once it is done, there is no way back to restore a previous cluster.
Keywords: clustering; divisive hierarchical clustering algorithms; DIANA algorithm.
A bioinspired multi-agent system based on monocular vision
by Evandro Luís Souza Falleiros, Renato Profirio Ishii, Rodrigo Calvo
Abstract: Develop multi-robot real-time applications is a complex task. In order to deal with such scenarios, this paper proposes PheroSLAM, a bio-inspired multi-robot system based on monocular camera, which adopt an extended version of ant colony optimisation approach to coordinate multiple-robot teams. Moreover, robots launch repulsive artificial pheromone around themself, creating a repulsive trail in PheroSLAM system. A vision-based mechanism is also used to provide visual odometry and to build a 3D feature-based map, considering that every robot must be able to localise itself in the explored environment. Therefore, the relevance of the proposal is to extend an SLAM problem for many robots and promote the robots move autonomously in the environment according a bio-inspired coordination strategy. Experimental evidences indicated the dispersibility of the PheroSLAM system, increasing the covered area of an environment. Also, results showed that the coordination strategy is efficient and satisfactory to accomplish the exploration task.
Keywords: Multi-Robot Systems; Multi-robot Framework; ROS applications.
Special Issue on: Soft Computational Approaches for Risk Exploration in Global Software Development
FPYM: development and application of a fuzzy-based Poka-Yoke model for the improvement of software performance
by K.K. Baseer, A. Rama Mohan Reddy, C. Shoba Bindu
Abstract: Improving qualities of software like reliability, availability, maintainability, cost, time and energy is key role in software development. These qualities are more dependable on the requirements, design, development, testing and deployment. In order to improve the software qualities on these cycles, avoiding mistakes or making alarm for each activity may be suitable choice. This is effectively studied using Poka-Yoke model which is applied in various production, manufacturing and software industries. Due to advantages of Poka-Yoke model, we have developed fuzzy-based Poka-Yoke model for small-scale software companies. This work aims to study the workflow and activities of two small scale companies involved in software development. In the case study, software performance attributes are defined and performance is analysed using four metrics called, UGAM, IOI, SM and SSM. The collected data is then extensively analysed to identify: the individual characteristics of companies, correlation behaviour of companies which they implemented the proposed model, improvement analysis over the period of time with the proposed model and forecasting the software performance for next products.
Keywords: software quality; Poka-Yoke; fuzzy logic; usability goals achievement metric; UGAM; index of integration; IOI; software performance.
Improving software reliability estimation using multi-layer neural-network combination model
by Indhurani Lakshmanan, Subburaj Ramasamy
Abstract: Software reliability growth models (SRGM) can be used to derive quantitative information about the quality of the product and also to estimate the software testing time needed to achieve target reliability. The modelling performance of SRGMs depends on the nature of the failure data set. In this paper, we propose a multi-layer feed-forward artificial neural network (ANN) combination model using two widely used generalised SRGMs as base models with back-propagation training algorithm. The proposed ANN-based model is compared with the traditional SRGMs and a few ANN based software reliability models. The performance comparison seems to confirm that, the goodness of fit and the predictive validity of proposed model appears to be better than that of reliability models compared. The proposed ANN-based model provides consistent performance for both exponential, and S-shaped growth of mean value function witnessed in software projects.
Keywords: software reliability growth models; SRGM; artificial neural network; ANN; software reliability estimation; the learning phenomenon of the testing team; generalised NHPP model.
Special Issue on: Recent Advances in Evolutionary Multi-Objective Optimisation
Vehicle routing multi-objective optimisation for hazardous materials transportation based on adaptive double populations genetic algorithm
by Changxi Ma, Ruichun He, Chengming Zhu, Xinfeng Yang, Fuquan Pan
Abstract: Aiming at hazardous materials transportation(HMT), vehicle routing optimisation models for single vehicle and multiple vehicle are proposed respectively, and the adaptive double populations genetic algorithm are constructed. Firstly, the goal function of models are minimizing the total risk, cost and the running time of hazardous materials vehicle. Then, the load constraint, max-risk constraint and time window constraint are considered. Finally, natural number is used for coding, double populations mechanism and adaptive weighted fitness allocation mechanism are adopted to calculate unit fitness, partial matched-crossover method is adopted for crossover operation, and the inversion mutation operator is adopted for mutation operation. Case study shows the model and algorithm are feasible, the vehicle routing strategy can provide direct reference for hazardous materials transportation decision-making departments and it is an effective way for prevention of hazardous materials transportation accidents.
Keywords: optimisation;vehicle routing problem;improved genetic algorithm;hazardous materials.
Hybrid algorithm for Two-objective Software Defect Prediction Problem
by Rong Xiaotao
Abstract: Static software defect prediction problem is one crucial problem in software test, to measure the performance, several indexes are introduced. In this paper, a two-objective software defect prediction model is employed, while probability of false alarm rate and probability of detection are taken as two objectives. To solve this model, one hybrid algorithm combined with support vector machine (SVM) and cuckoo search algorithm is designed. SVM is one general tool for this problem, and the performance is significantly influenced by two parameters. To provide a good classification results, one multi-objective cuckoo search algorithm is designed to optimize these two parameters. In this algorithm, the global best position is extended to be one collection including all non-dominated solutions, and the local search manner is changed to increase the local search speed. Simulation results show our hybrid algorithm is effective.
Keywords: support vector machine; software defect prediction; multi-objective cuckoo search.
Measurement method and application of design adaptability for product platform based on information content
by Xianfu Cheng, Gaofeng Liang, Chong Wan
Abstract: Product platform has been recognized as an effective means to achieve mass customization. A key feature affecting the success of a product family is the effectiveness of the product platform across diverse market segments. Adaptable design is a design methodology to create designs and products that can be easily adapted to meet a diversity of requirements. The product platform with adaptability provides a basis for the modification, evolvement and upgrading of product family. This paper focuses on design adaptability issue of product platform, that is, to evaluate the cost effectiveness of a product design to be adapted to meet individual customer demands. Four aspects of adaptability are considered, namely, reusability, customizability, interface flexibility and upgradeability. Product platform adaptability was measured based on the information content metric. Finally, a case study is given to demonstrate the effectiveness and feasibility of the proposed method
Keywords: product platform; design adaptability; information content; adaptability degree.
Firefly algorithm for multi-objective optimal allocation of water resource
by Wenjun Wang, Dongxiao Liu, Hui Wang
Abstract: Firefly algorithm (FA) is a new optimization technique based on swarm intelligence, which has been successfully applied to various optimization areas. In this paper, a new FA variant is proposed to solve multi-objective optimal allocation of water resource, in which three objectives, including economic, social, and environmental benefits, are maximized. To obtain the Pareto fronts, the original FA is combined with the fast non-dominated sorting method used in NSGA-II. Simulation results show that our approach can achieve a good spacing of solution points along the Pareto Front. According to the preferences, the decision makers can choose different allocation methods from the Pareto front.
Keywords: firefly algorithm; multi-objective optimization; water resources; optimal allocation.
Multi-level Assembly Process Complexity analysis and its application for Mixed-model Assembly Sequencing
by He Fei, Jiang Mingming
Abstract: This research aims at understanding the process complexity in assembly system, and the complexity is defined to describe the complexity for the production activities and their sequences. Four primary integer layers and other fractal layers are decomposed from the whole assembly process according to the idea of fractal theory. Four kinds of complexities are station operation complexity, assembly flow complexity, production sequence complexity and production cycle complexity, they are proposed to present the complexity characteristic for different integer layers. The information entropy is adopted to measure these process complexities, and two different measurements are proposed for the pull and push production models respectively. For conquering the two contradictory problems, high operation failure rate and decrease of working emotion, which are caused by inappropriate product similarity distribution, the optimization objective minimizing the diversity of the assembly flow complexity is exploited. Then the multi-objective genetic algorithm is adopted to modeling the mixed-model assembly sequencing problem with two optimization objectives, and a case study is implemented to demonstrate the approach.
Keywords: Process Complexity; information entropy; Assembly System; Fractal Idea; Mixed-model Assembly Sequencing.
Hardware Implementation of Multi-Objective Differential Evolution algorithm: A Case Study of Spectrum Allocation in Cognitive Radio Networks
by Kiran Kumar Anumandla, Rangababu Peesapati, Sabat Samrat L
Abstract: In this paper, a hardware solution for multi-objective differential evolution (MODE) algorithm is presented. The hardware is used to solve multi-objective optimization problem and a set of pareto optimal solutions are obtained. The proposed hardware is developed as a co-processor and interfaced with PowerPC440 processor of Virtex-5 Field Programmable Gate Array to accelerate the execution speed of the MODE algorithm on an embedded platform. The functionality of the MODE core is validated by optimizing two standard benchmark functions. Then, the execution time of the MODE core is compared with the execution time of the same algorithm on a 32-bit RISC PowerPC440 processor of Virtex-5 FPGA. Further, as a case study, the proposed hardware is used to solve spectrum allocation (SA) problem in cognitive radio networks. In cognitive radio network, the available licensed channels are assigned to cognitive users using spectrum allocation task by satisfying the multiple objectives to provide best channels rnwithout interference to primary users. The MODE core is integrated with the SA objective functions and developed as a MODE based SA (MODE-SA) co-processor on an embedded platform for distributed cognitive radio network. The MODE-SA core has attained a speedup of 50-60x compared to the PowerPC440 processor to complete the allocation process.
Keywords: FPGA; Multi-Objective Differential Evolution; Hardware Accelerator; Spectrum Allocation; Cognitive Radio.