International Journal of Innovative Computing and Applications (15 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
An Empirical Study of Statistical Language Models: N-gram Language Models vs. Neural Network Language Models
by Freha MEZZOUDJ, Abdelkader BENYETTOU
Abstract: Statistical language models are an important module in many areas of successful applications such as speech recognition and machine translation. And N-gram models are basically the state-of-the-art. However, due to sparsity of data, the modelled language cannot be completely represented in the n-gram language model. In fact, if new words appear in the recognition or translation steps, we need to provide a smoothing method to distribute the model probabilities over the unknown values. Recently, neural networks were used to model language based on the idea of projecting words onto a continuous space and performing the probability estimation in this space. In this experimental work, we compare the behavior of the most popular smoothing methods with statistical n-gram language models and neural network language models in different situations and with different parameters. The language models are trained on two corpora of French and English texts. Good empirical results are obtained by the recurrent neural network language models.
Keywords: language models; n-grams; Kneser-Ney smoothing; modified Kneser-Ney smoothing; Good-Turing smoothing; interpolation; back-off ; feed-forward neural networks; continuous space language models; recurrent neural networks; speech recognition; machine translation.
Blind Hyperspectral Unmixing by Nonparametric Non-Gaussianity Measure
by Fasong WANG
Abstract: For linear mixing model (LMM) of hyperspectral unmixing (HU) in hyperspectral images processing problem, the endmember fractional abundances satisfy the sum-to-one constraint, which makes the well-known independent component analysis (ICA) based blind source separation (BSS) algorithms not well suited to blind hyperspectral unmixing (bHU). A novel nonparametric bHU approach consulting dependent component analysis (DCA) is presented in this paper. The novel cost function is derived based on the cumulative density function (CDF) and order statistics (OS) instead of traditional probability density function (PDF). By executing the stochastic gradient rule of constrained optimization method, the efficient dependent sources separation algorithm for bHU is obtained to fulfill the endmember signatures extraction and abundances estimation tasks. Simulations based on the synthetic data are performed to evaluate the validity of the proposed nonpNG-bHU algorithm.
Keywords: independent component analysis (ICA); blind source separation (BSS); blind hyperspectral unmixing (bHU); dependent component analysis (DCA).
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.