A bacteria foraging algorithm based cell formation considering operation time

The cellular manufacturing system (CMS) is considered as an efficient production strategy for batch type production. The CMS relies on the principle of grouping machines into machine cells and grouping machine parts into part families based on pertinent similarity measures. The bacteria foraging algorithm (BFA) is a new in development computation technique extracted from the social foraging behavior of Escherichia coli (E. coli) bacteria. Ever since Kevin M. Passino invented the BFA, one of the main challenges has been employment of the algorithm to problem areas other than those for which the algorithm was proposed. This research work inquires the first applications of this emerging novel optimization algorithm to the cell formation (CF) problem. In addition, a newly developed BFA-based optimization algorithm for CF is discussed. In this paper, an attempt is made to solve the cell formation problem meanwhile taking into consideration number of voids in cells and a number of exceptional elements based on operational time of the parts required for processing in the machines. The BFA is suggested to create machine cells and part families. The performance of the proposed algorithm is compared with a number of algorithms that are most commonly used and reported in the corresponding scientific literature such as similarity coefficients methods (SCM), rank order clustering (ROC), ZODIAC, GRAFICS, MST, GATSP, GP, K-harmonic clustering (KHM), K-means clustering, C-link clustering, modified ART1, GA (genetic algorithm), evolutionary algorithm (EA), and simulated annealing (SA) using defined performance measures known as modified grouping efficiency and grouping efficacy. The results lie in favor of better performance of the proposed algorithm.     

BASE: A bacteria foraging algorithm for cell formation with sequence data

A cellular manufacturing system (CMS) is considered an efficient production strategy for batch type production. A CMS relies on the principle of grouping machines into machine cells and grouping parts into part families on the basis of pertinent similarity measures. The bacteria foraging algorithm (BFA) is a newly developed computation technique extracted from the social foraging behavior of Escherichia coli (E. coli) bacteria. Ever since Kevin M. Passino invented the BFA, one of the main challenges has been employment of the algorithm to problem areas other than those for which the algorithm was proposed. This research work studies the first applications of this emerging novel optimization algorithm to the cell formation (CF) problem considering the operation sequence. In addition, a newly developed BFA-based optimization algorithm for CF based on operation sequences is discussed. In this paper, an attempt is made to solve the CF problem, while taking into consideration the number of voids in the cells and the number of inter-cell travels based on operational sequences of the parts visited by the machines. The BFA is suggested to create machine cells and part families. The performance of the proposed algorithm is compared with that of a number of algorithms that are most commonly used and reported in the corresponding scientific literature, such as the CASE clustering algorithm for sequence data, the ACCORD bicriterion clustering algorithm and modified ART1, and using a defined performance measure known as group technology efficiency and bond efficiency. The results show better performance of the proposed algorithm.     

A novel bacterial foraging optimization algorithm for feature selection

Bacterial foraging optimization (BFO) algorithm is a new swarming intelligent method, which has a satisfactory performance in solving the continuous optimization problem based on the chemotaxis, swarming, reproduction and elimination-dispersal steps. However, BFO algorithm is rarely used to deal with feature selection problem. In this paper, we propose two novel BFO algorithms, which are named as adaptive chemotaxis bacterial foraging optimization algorithm (ACBFO) and improved swarming and elimination-dispersal bacterial foraging optimization algorithm (ISEDBFO) respectively. Two improvements are presented in ACBFO. On the one hand, in order to solve the discrete problem, data structure of each bacterium is redefined to establish the mapping relationship between the bacterium and the feature subset. On the other hand, an adaptive method for evaluating the importance of features is designed. Therefore the primary features in feature subset are preserved. ISEDBFO is proposed based on ACBFO. ISEDBFO algorithm also includes two modifications. First, with the aim of describing the nature of cell to cell attraction-repulsion relationship more accurately, swarming representation is improved by means of introducing the hyperbolic tangent function. Second, in order to retain the primary features of eliminated bacteria, roulette technique is applied to the elimination-dispersal phase.In this study, ACBFO and ISEDBFO are tested with 10 public data sets of UCI. The performance of the proposed methods is compared with particle swarm optimization based, genetic algorithm based, simulated annealing based, ant lion optimization based, binary bat algorithm based and cuckoo search based approaches. The experimental results demonstrate that the average classification accuracy of the proposed algorithms is nearly 3 percentage points higher than other tested methods. Furthermore, the improved algorithms reduce the length of the feature subset by almost 3 in comparison to other methods. In addition, the modified methods achieve excellent performance on wilcoxon signed-rank test and sensitivity-specificity test. In conclusion, the novel BFO algorithms can provide important support for the expert and intelligent systems.     

A hybrid genetic-variable neighborhood search algorithm for the cell formation problem based on grouping efficacy

Cell formation problem attempts to group machines and part families in dedicated manufacturing cells such that the number of voids and exceptional elements in cells are minimized. In this paper, we presented a linear fractional programming model with the objective of maximizing the grouping efficacy while the number of cells is unknown. To show the effectiveness of the proposed model, two test problems were applied. Then, to solve the model for real-sized applications, a hybrid meta-heuristic algorithm in which genetic algorithm and variable neighborhood search are combined. Using the grouping efficacy measure, we have also compared the performance of the proposed algorithm on a set of 35 test problems from the literature. The results show that the proposed GA-VNS method outperforms the state-of-the-art algorithms.     

Two-stage approach for machine-part grouping and cell layout problems

Cellular manufacturing system (CMS) which is based on the concept of group technology (GT) has been recognized as an efficient and effective way to improve the productivity in a factory. In recent years, there have been continuous research efforts to study different facet of CMS. Most of them concentrated on distinguishing the part families and machine cells either simultaneously or individually with the objective of minimizing intercellular and intracellular part movements. This is known as machine-part grouping problem (MPGP) which is a crucial process while designing CMS. Nevertheless, in reality some components may not be finished within only one cell, they have to travel to another cell(s) for further operation(s). Under this circumstance, intercellular part movement will occur. Different order/sequence of machine cells allocation may result in different total intercellular movement distance unit. It should be noted that if the production volume of each part is very large, then the total number of intercellular movement will be further larger. Therefore, the sequence of machine cells is particularly important in this aspect. With this consideration, the main aim of this work is to propose two-stage approach for solving cell formation problem as well as cell layout problem. The first stage is to identify machine cells and part families, which is the essential part of MPGP. The work in second stage is to carry out a macro-approach to study the cell formation problem with consideration of machining sequence. The impact of the sequencing for allocating the machine cells on minimizing intercellular movement distance unit will be investigated in this stage. The problem scope, which is a MPGP together with the background of cell layout problem (CLP), has been identified. Two mathematical models are formulated for MPGP and CLP respectively. The primary assumption of CLP is that it is a linear layout. The CLP is considered as a quadratic assignment problem (QAP). As MPGP and QAP are NP-hard, genetic algorithm (GA) is employed as solving algorithm. GA is a popular heuristic search technique and has proved superior performance on complex optimization problem. In addition, an industrial case study of a steel member production company has been employed to evaluate the proposed MPGP and CLP models, and the computational results are presented.     

Evolutionary state-based novel multi-objective periodic bacterial foraging optimization algorithm for data clustering

Clustering divides objects into groups based on similarity. However, traditional clustering approaches are plagued by their difficulty in dealing with data with complex structure and high dimensionality, as well as their inability in solving multi-objective data clustering problems. To address these issues, an evolutionary state-based novel multi-objective periodic bacterial foraging optimization algorithm (ES-NMPBFO) is proposed in this article. The algorithm is designed to alleviate the high-computing complexity of the standard bacterial foraging optimization (BFO) algorithm by introducing periodic BFO. Moreover, two learning strategies, global best individual (gbest) and personal historical best individual (pbest), are used in the chemotaxis operation to enhance the convergence speed and guide the bacteria to the optimum position. Two elimination-dispersal operations are also proposed to prevent falling into local optima and improve the diversity of solutions. The proposed algorithm is compared with five other algorithms on six validity indexes in two data clustering cases comprising nine general benchmark datasets and four credit risk assessment datasets. The experimental results suggest that the proposed algorithm significantly outperforms the competing approaches. To further examine the effectiveness of the proposed strategies, two variants of ES-NMPBFO were designed, and all three forms of ES-NMPBFO were tested. The experimental results show that all of the proposed strategies are conducive to the improvement of solution quality, diversity and convergence.     

Bacterial Foraging Optimization Approach to Portfolio Optimization

In this paper we propose a heuristic approach based on bacterial foraging optimization (BFO) in order to find the efficient frontier associated with the portfolio optimization (PO) problem. The PO model with cardinality and bounding constraints is a mixed quadratic and integer programming problem for which no exact algorithms can solve in an efficient way. Consequently, various heuristic algorithms, such as genetic algorithms and particle swarm optimization, have been proposed in the past. This paper aims to examine the potential of a BFO algorithm in solving the PO problem. BFO is a new swarm intelligence technique that has been successfully applied to several real world problems. Through three operations, chemotaxis, reproduction, and elimination-dispersal, the proposed BFO algorithm can effectively solve a PO problem. The performance of the proposed approach was evaluated in computational tests on five benchmark data sets, and the results were compared to those obtained from existing heuristic algorithms. The proposed BFO algorithm is found to be superior to previous heuristic algorithms in terms of solution quality and time.     

Manufacturing cell formation with production data using neural networks

Batch type production strategies need adoption of cellular manufacturing (CM) in order to improve operational effectiveness by reducing manufacturing lead time and costs related to inventory and material handling. CM necessitates that parts are to be grouped into part families based on their similarities in manufacturing and design attributes. Then, machines are allocated into machine cells to produce the identified part families so that productivity and flexibility of the system can be improved. Zero-one part-machine incidence matrix (PMIM) generated from route sheet information is commonly presented as input for clustering of parts and machines. An entry of ‘1’ in PMIM indicates that the part is visiting the machine and zero otherwise. The output is generated in the form of block diagonal structure where each block represents a machine cell having more than one machines and a part family. The major limitations of this approach lies in the fact that important production factors like operation time, sequence of operations, and lot size of the parts are not accounted for. In this paper, an attempt has been made to propose a clustering methodology based on adaptive resonance theory (ART) for addressing these issues. Initially, a methodology considering only the operation sequence of the parts has been proposed. Then, the methodology is suitably modified to deal with combination of operation sequence and operation time of the parts to address generalized cell formation (CF) problem. A new performance measure is proposed to quantify the performance of the proposed methodology. The performance of the proposed algorithm is tested with benchmark problems from open literature and the results are compared with the existing methods. The results clearly indicate that the proposed methodology outperforms the existing methods in most cases.     

Minimization of exceptional elements and voids in the cell formation problem using a multi-objective genetic algorithm

Cell formation problem is the main issue in designing cellular manufacturing systems. The most important objective in the cell formation problem is to minimize the number of exceptional elements which helps to reduce the number of intercellular movements. Another important but rarely used objective function is to minimize the number of voids inside of the machine cells. This objective function is considered in order to increase the utilization of the machines. We present a bi-objective mathematical model to simultaneously minimize the number of exceptional elements and the number of voids in the part machine incidence matrix. An ε-constraint method is then applied to solve the model and to generate the efficient solutions. Because of the NP-hardness of the model, the optimal algorithms can not be used in large-scale problems and therefore, we have also developed a bi-objective genetic algorithm. Some numerical examples are considered to illustrate the performance of the model and the effectiveness of the solution algorithms. The results demonstrate that in comparison with the ε-constraint method, the proposed genetic algorithm can obtain efficient solution in a reasonable run time.     

基于细菌觅食优化算法的城市轨道交通调度优化

为了合理高效地制定城市轨道交通调度方案,实现客流与车次的优化配置,提出了一种基于细菌觅食优化算法的城市轨道交通调度优化策略。兼顾乘客与运营企业双方利益,以发车间隔为决策变量,乘客平均候车时间最短和发车次数最少为优化目标,建立调度优化模型,并对细菌觅食优化算法求解该调度模型的过程进行分析。结合某城市轨道交通一号线实际运营数据进行仿真实验,并与其他算法的优化结果进行对比分析,实验表明该算法和模型能有效解决城市轨道交通调度优化问题。     

基于Relief和BFO的并行支持向量机算法

针对大数据环境下并行支持向量机(SVM)算法存在冗余数据敏感、参数选取困难、并行化效率低等问题,提出了一种基于Relief和BFO算法的并行SVM算法RBFO-PSVM。首先,基于互信息和Relief算法设计了一种特征权值计算策略MI-Relief,剔除数据集中的冗余特征,有效地降低了冗余数据对并行SVM分类的干扰;接着,提出了基于MapReduce的MR-HBFO算法,并行选取SVM的最优参数,提高SVM的参数寻优能力;最后,提出核聚类策略KCS,减小参与并行化训练的数据集规模,并提出改进CSVM反馈机制的交叉融合级联式并行支持向量机CFCPSVM,结合MapReduce编程框架并行训练SVM,提高了并行SVM的并行化效率。实验表明,RBFO-PSVM算法对大型数据集的分类效果更佳,更适用于大数据环境。     

A hybrid method based on genetic algorithm and dynamic programming for solving a bi-objective cell formation problem considering alternative process routings and machine duplication

Cell formation is one of the first and most important steps in designing a cellular manufacturing system. It consist of grouping parts with similar design features or processing requirements into part families and associated machines into machine cells. In this study, a bi-objective cell formation problem considering alternative process routings and machine duplication is presented. Manufacturing factors such as part demands, processing times and machine capacities are incorporated in the problem. The objectives of the problem include the minimization of the total dissimilarity between the parts and the minimization of the total investment needed for the acquisition of machines. A normalized weighted sum method is applied to unify the objective functions. Due to the computational complexity of the problem, a hybrid method combining genetic algorithm and dynamic programming is developed to solve it. In the proposed method, the dynamic programming is implemented to evaluate the fitness value of chromosomes in the genetic algorithm. Computational experiments are conducted to examine the performance of the hybrid method. The computations showed promising results in terms of both solution quality and computation time.     

细菌觅食算法求解高维优化问题

针对细菌觅食优化算法中,以往的自适应步长公式引入参数过多,统一的经验性参数无法适应各类不同问题的情况,提出了改进的自适应步长公式,通过在步长公式中引入当前细菌的进化代数、寻优范围,并发挥当前最优细菌的引导作用,灵活的调整步长,真正达到自适应调整步长的目的;其次对高维优化问题进行分析,将其分为可分解可分组、不可分解可分组和不可分解不可分组三大类,针对不同类型的问题,采用不同的分组方式,降维、细化来求解,将复杂的问题简单化,极大的提高了求解的效率和精度。将改进的自适应步长公式应用于高维优化问题的求解方法中,通过对多个标准测试函数在多维空间特别是超高维空间（500维、800维、1000维）进行测试,并将其结果同其它算法进行比较,实验证明本文改进算法在寻得最优解的精度和效率上比其它改进方案有显著提高。     

基于细菌觅食优化算法的WSNs节点部署策略

为了提高传感器节点的有效覆盖率,提出了一种基于细菌觅食优化(BFO)算法的节点部署策略。以网络覆盖率为目标函数,在细菌觅食算法的趋向操作过程中,引入碰壁策略,对细菌初始位置进行优化,从而提高算法的收敛速度。算法中的每个细菌都代表一只传感器,多个细菌组成的一个菌落代表一种传感器的部署方案。算法以菌落为单位做复制操作和迁徙操作,按照菌落适应度值大小选出较为优越的部署方案。通过仿真实验,分析了参数对算法性能的影响,并与其他方法的优化结果进行比较,结果表明:该算法有效地提高了传感器节点覆盖率。     

Automatic image pixel clustering with an improved differential evolution

This article proposes an evolutionary-fuzzy clustering algorithm for automatically grouping the pixels of an image into different homogeneous regions. The algorithm does not require a prior knowledge of the number of clusters. The fuzzy clustering task in the intensity space of an image is formulated as an optimization problem. An improved variant of the differential evolution (DE) algorithm has been used to determine the number of naturally occurring clusters in the image as well as to refine the cluster centers. We report extensive performance comparison among the new method, a recently developed genetic-fuzzy clustering technique and the classical fuzzy c-means algorithm over a test suite comprising ordinary grayscale images and remote sensing satellite images. Such comparisons reveal, in a statistically meaningful way, the superiority of the proposed technique in terms of speed, accuracy and robustness.     

A novel approach to determine cell formation,intracellular machine layout and cell layout in the CMS problem based on TOPSIS method

This paper deals with the cellular manufacturing system (CMS) that is based on group technology (GT) concepts. CMS is defined as identifying the similar parts that are processed on the same machines and then grouping them as a cell. The most proposed models for solving CMS problems are focused on cell formation and intracellular machine layout problem while cell layout is considered in few papers. In this paper we apply the multiple attribute decision making (MADM) concept and propose a two-stage method that leads to determine cell formation, intracellular machine layout and cell layout as three basic steps in the design of CMS. In this method, an initial solution is obtained from technique for order preference by similarity to the ideal solution (TOPSIS) and then this solution is improved. The results of the proposed method are compared with well-known approaches that are introduced in literature. These comparisons show that the proposed method offers good solutions for the CMS problem. The computational results are also reported.     

动态高斯变异和随机变异融合的自适应细菌觅食优化算法

针对细菌觅食优化(Bacterial Foraging Optimization,BFO)算法在高维函数优化上性能较差和普适性不强的问题,提出一种动态高斯变异和随机变异融合的自适应细菌觅食优化算法.首先,将原随机迁徙方案修改为动态高斯变异与随机变异融合的迁徙方法,即搜索前期利用随机迁徙有利于增加解的多样性,获得全局最优解,搜索后期改用动态的高斯变异来提高算法的收敛速度;然后,对趋化操作中的步长参数使用动态调整和自适应调整来增强算法的普适性;最后,构建全局极值感应机制使优化更有效,从而获得了一种高性能的自适应BFO算法,以便能够高效解决高维函数的优化问题.14个高维函数优化的仿真结果表明,提出的算法不仅优化效果好、普适性强,而且能以更快的速度找到全局最优解,性能优于SBFO、POLBBO、BFAVP和RABC算法.     

A genetic-algorithm-based heuristic for the GT cell formation problem

This paper presents a heuristic for the machine-part grouping problem which incorporates relevant production requirements such as routing sequence, production volume, unit handling size, unit processing time and cell size. The heuristic consists of two phases. The first phase is developed based on a genetic algorithm and greedy heuristic to solve the machine grouping problem. Once machine cells are identified, the second phase is employed to identify the associated part families. The performance of the heuristic is examined through a comparative study with some existing solution methods. Global efficiency, group efficiency, intercell move factor and grouping effectiveness are adopted as comparative measures.     

An efficient approach to determine cell formation,cell layout and intracellular machine sequence in cellular manufacturing systems

Cellular manufacturing systems (CMS) are used to improve production flexibility and efficiency. They involve the identification of part families and machine cells so that intercellular movement is minimized and the utilization of the machines within a cell is maximized. Previous research has focused mainly on cell formation problems and their variants; however, only few articles have focused on more practical and complicated problems that simultaneously consider the three critical issues in the CMS-design process, i.e., cell formation, cell layout, and intracellular machine sequence. In this study, a two-stage mathematical programming model is formulated to integrate the three critical issues with the consideration of alternative process routings, operation sequences, and production volume. Next, because of the combinatorial nature of the above model, an efficient tabu search algorithm based on a generalized similarity coefficient is proposed. Computational results from test problems show that our proposed model and solution approach are both effective and efficient. When compared to the mathematical programming approach, which takes more than 112 h (LINGO) and 1139 s (CPLEX) to solve a set of ten test instances, the proposed algorithm can produce optimal solutions for the same set of test instances in less than 12 s.     

A hybrid grouping genetic algorithm for the cell formation problem

The machine-part cell formation problem consists of constructing a set of machine cells and their corresponding product families with the objective of minimizing the inter-cell movement of the products while maximizing machine utilization. This paper presents a hybrid grouping genetic algorithm for the cell formation problem that combines a local search with a standard grouping genetic algorithm to form machine-part cells. Computational results using the grouping efficacy measure for a set of cell formation problems from the literature are presented. The hybrid grouping genetic algorithm is shown to outperform the standard grouping genetic algorithm by exceeding the solution quality on all test problems and by reducing the variability among the solutions found. The algorithm developed performs well on all test problems, exceeding or matching the solution quality of the results presented in previous literature for most problems.