International Conference Papers
Permanent URI for this collectionhttp://dl.cerist.dz/handle/CERIST/4
Browse
17 results
Search Results
Item Impact of Genetic Algorithms Operators on Association Rules Extraction(2016-11-11) Hamdad, Leila; Ournani, Zakaria; Benatchba, Karima; Bendjoudi, AhcèneIn this paper we study the impact of GAs’ components such as encoding, different crossover, mutation and replacement strategies on the number of extracted association rules and their quality. Moreover, we propose a strategy to manage the population. The later is organized in classes where each one encloses same size rules. Each class can be seen as a population on which a GA is applied. All tests are conducted on two types of benchmarks : synthetic and real ones of different sizes.Item Efficient parallel B&B method for the Blocking Job Shop Scheduling Problem(2016-07) Dabah, Adel; Bendjoudi, Ahcène; Ait Zai, AbdelhakimThe blocking job shop scheduling problem (BJSS) is a version of the classical job shop scheduling with no intermediate buffer between machines. It is known to be NP-hard in the strong sense. The major drawbacks of the previous works are the huge time needed to explore the search space and the low ratio of feasible to explored solutions when applying metaheuristics, leading to a poor quality of final solutions. In order to accelerate the exploration of the search space and overcome the drawback of metaheuristics, we propose in this paper a parallel Branch and Bound (B&B) algorithm to act both as an exact or approximate methods. The proposed parallel B&B approach is based on the master-worker paradigm, exploiting the computing power offered by cluster architectures. The master performs a breadth-first exploration to ensure high availability of tasks (sub-problems) while the workers perform a depth-first exploration in order to browse a large number of feasible solutions, therefore, obtaining a faster improvement of the solution quality. The proposed approach has been executed on a cluster based architecture using 32 nodes with 16 CPU cores each. The obtained results show a good speedup of the execution time with 80% efficiency. We have been able to solve optimally ten BJSS benchmark instances never solved before. Moreover, our proposed approach improved the best solutions for more than 22 benchmark instances.Item Multi and Many-core Parallel B&B approaches for the Blocking Job Shop Scheduling Problem(2016-07) Dabah, Adel; Bendjoudi, Ahcène; Ait Zai, Abdelhakim; El Baz, Didier; Nouali-Taboudjemat, NadiaIn this paper, we propose three approaches to accelerate the B&B execution time using Multi and Many-core systems to solve the NP-hard Blocking Job Shop Scheduling problem (BJSS). The first approach is based on Master/Worker paradigm where the workers independently explore the branches sent by the master. The second approach is a node-based parallelization that does not change the design of the B&B algorithm, except that the bounding process is faster since it is calculated in parallel using several threads organized in one GPU block. The third approach is a Multi-Core CPU/GPU hybridization that benefits from the power of both the CPU-cores and the GPU at the same time. This hybridization is based on concurrent kernels execution provided by Nvidia Multi process Service (MPS) i.e. each host process (Master or Worker) launches his own kernel to accelerate the bounding process on GPU. The obtained results using Taillard instances confirm the efficiency of our proposals. The first two approaches are respectively three and eighteen times faster compared to the sequential version. The results of the hybrid approach show a relative speedup over ninety times as compared to the sequential approach and therefore prove the advantage of using both the CPU-cores and the GPU at the same time.Item Parallel BSO Algorithm for Association Rules Mining Using Master/Worker Paradigm(2015-09-06) Djenouri, Youcef; Bendjoudi, Ahcène; Djenouri, Djamel; Habbas, ZinebThe extraction of association rules from large transactional databases is considered in the paper using cluster architecture parallel computing. Motivated by both the successful sequential BSO-ARM algorithm, and the strong matching between this algorithm and the structure of the cluster architectures, we present in this paper a new parallel ARM algorithm that we call MW-BSO-ARM for Master/Workers version of BSO-ARM. The goal is to deal with large databases by minimizing the communication and synchronization costs, which represent the main challenges that faces any cluster architecture. The experimental results are very promising and show clear improvement that reaches 300% for large instances. For examples, in big transactional database such as WebDocs, the proposed approach generates 107 satisfied rules in only 22 minutes, while a previous GPU-based approach cannot generate more than 103 satisfied rules into 10 hours. The results also reveal that MWBSO-ARM outperforms the PGARM cluster-based approach in terms of computation time.Item GPU-based two level parallel B&B for the Blocking job shop scheduling problem.(IEEE, 2016-05-23) Adel, Dabah; Bendjoudi, Ahcène; El Baz, Didier; Abdelhakim, Ait ZaiBranch and bound algorithms (B&B) are well known techniques for solving optimally combinatorial optimization problems. Nevertheless, these algorithms remain inefficient when dealing with large instances. This paper deals with the blocking job shop scheduling (BJSS), which is a version of classical job shop scheduling with no intermediate buffer between machines. This problem is an NP-hard problem and its exact resolution using the sequential approach is impractical. We propose in this paper a GPU-based parallelization in which a two level scheme is used. The first level is a node-based parallelization in which the bounding process is faster because it is calculated in parallel using several threads organized in one GPU block. To fully occupy the GPU, we propose a second level of parallelization which is a generalization of the first level. Therefore, for each iteration several search tree nodes are evaluated on the GPU using several thread-blocks. The obtained results, using the well-known Taillard instances, confirm the efficiency of the proposed approach. Also, the results show that our approach is 65 times faster than an optimized sequential B&B version.Item Data reordering for minimizing threads divergence in GPU-based evaluating association rules(2015-06) Djenouri, Youcef; Bendjoudi, Ahcène; Mehdi, Malika; Habbas, Zineb; Nouali-Taboudjemat, NadiaThis last decade, the success of Graphics Processor Units (GPUs) has led researchers to launch a lot of works on solving large complex problems by using these cheap and powerful architecture. Association Rules Mining (ARM) is one of these hard problems requiring a lot of computational resources. Due to the exponential increase of data bases size, existing algorithms for ARM problem become more and more inefficient.Thus, research has been focusing on parallelizing these algorithms. Recently, GPUs are starting to be used to this task. However, their major drawback is the threads divergence problem. To deal with this issue, we propose in this paper an intelligent strategy called transactions-based Reordering ”TR” allowing an efficient evaluation of association rules on GPU by minimizing threads divergence. This strategy is based on data base re-organization. To validate our proposition, theoretical and experimental studies have been carried out using well-known synthetic datasets. The results are very promising in terms of minimizing the number of threads divergence.Item Association rules mining using evolutionary algorithms(LNCS, 2014-10-16) Djenouri, Youcef; Bendjoudi, Ahcène; Nouali-Taboudjemat, NadiaThis paper deals with association rules mining using evolutionary algorithms. All previous bio-inspired based association rules mining approaches generate non admissible rules which the end-user can not exploit them. In this paper, we propose two approaches permit to avoid non admissible rules by developing new strategy called delete and decomposition strategy. If an item is appeared in the antecedent and the consequent parts of given rule, this rule is composed on two admissible rules. Then, we delete such item to the antecedent part of the first rule and we delete the same item to the consequent part of the second rule. We also proposed two approaches (IARMGA and IARMMA), the first approach uses a classical genetic algorithm in the search process. However, the second one employs a mimetic algorithm to improve the quality of returned rules. To demonstrate the suggested approaches, several experiments have been carried out using both synthetic and reals instances. The results reveal that it has a compromise between the execution time and the quality of output rules. Indeed, IARMGA is faster than IARMMA whereas the last one outperforms IARMGA in terms of rules quality.Item An Efficient Measure for Evaluating Association Rules(2014-08) Djenouri, Youcef; Gheraibai, Youcef; Mehdi, Malika; Bendjoudi, AhcèneAssociation rules mining (ARM) has attracted a lot of attention in the last decade. It aims to extract a set of relevant rules from a given database. In order to evaluate the quality of the resulting rules, existing measures, such as support and confidence, allow to evaluate the resulted rules of ARM process separately, missing the different dependencies between the rules. This paper addresses the problem of evaluating rules by taking into account two aspects: (1) The accuracy of the returned rules on the input data and (2) the distance between the returned rules. The rules set that covers the maximum of rules space is considered. To analyze the behavior of the proposed measure, it has been tested on two recent ARM algorithms BSO-ARM and HBSO-TS.Item Parallel Rules Mining Using GPUs and Bees Behaviors(2014-08) Djenouri, Youcef; Bendjoudi, Ahcène; Mehdi, Malika; Nouali-Taboudjemat, Nadia; Habbas, ZinebThis paper addresses the problem of association rules mining with large data sets using bees behaviors. The bees swarm optimization method have been successfully applied on small and medium data size. Nevertheless, when dealing Webdocs benchmark (the largest benchmark on the web), it is bluntly blocked after more than 15 days. Additionally, Graphic processor Units are massively threaded providing highly intensive computing and very usable by the optimization research community. The parallelization of such method on GPU architecture can be deal large data sets as the case of WebDocs in real time. In this paper, the evaluation process of the solutions is parallelized. Experimental results reveal that the suggested method outperforms the sequential version at the order of ×100 in most data sets, furthermore, the WebDocs benchmark is handled with less than ten hours.Item Towards a Dynamic Evacuation System for Disaster Situations(IEEE, 2014-03) Benssam, Ali; Bendjoudi, Ahcène; Yahiaoui, Saïd; Nouali-Taboudjemat, Nadia; Nouali, OmarMedical evacuation is one of the most important modules in the emergency plans activated during disaster situations. It aims at evacuating victims to the most appropriate health-care facilities. Evacuation plans were for a long time performed approximatively and passively rather than optimally and proactively between the disposal site and the targeted hospital and they often lacked visibility on the evolution of the events that may change data and leading to a revision of the plans. However, thanks to the proliferation of information and communication technologies (ICTs) in all aspects of life, the evacuation operations in disaster situations had known a great enhancement. In fact, critical operations such as real-time monitoring of the state of resources used during the evacuation process, detecting the occurring changes and reflecting them on the global process to provide dynamic and optimal evacuation plans become possible. In this paper, we propose a framework for dynamic evacuation operations in disaster situations. We design a system that takes into consideration the above challenges such as detecting changes and using them in an intelligent way to enable dynamic, optimal and up-to-date evacuation plans. The provided prototype is called DEvacuS (Dynamic Evacuation System).