COURSE TIMETABLING AT A TUNISIAN UNIVERSITY： A CASE STUDY

This paper deals with the Course Timetabling Problem at an institution in a Tunisian University. We introduce a heuristic procedure to construct a feasible timetable for all lectures and tutorials taken by different groups of each sub-section of any section. We describe the timetabling problem using a list of all specific hard and soft constraints. We formulate the problem as a set of linear constraints using two sets of binary variables corresponding to lectures and tutorials, respectively. This heuristic is illustrated with real data for a sub-section of the Faculty of Economics and Management Sciences of Sfax in Tunisia, and the resulting timetables are compared with those generated manually. The results of another full section have confirmed the good quality of the proposed heuristic when compared with the hand made solution.     

Memetic algorithm for multi-mode resource-constrained project scheduling problems

A memetic algorithm （MA） for a multi-mode resourceconstrained project scheduling problem （MRCPSP） is proposed. We use a new fitness function and two very effective local search procedures in the proposed MA. The fitness function makes use of a mechanism called ＂strategic oscillation＂ to make the search process have a higher probability to visit solutions around a ＂feasible boundary＂. One of the local search procedures aims at improving the lower bound of project makespan to be less than a known upper bound, and another aims at improving a solution of an MRCPSP instance accepting infeasible solutions based on the new fitness function in the search process. A detailed computational experiment is set up using instances from the problem instance library PSPLIB. Computational results show that the proposed MA is very competitive with the state-of-the-art algorithms. The MA obtains improved solutions for one instance of set J30.     

A rough set approach to feature selection based on scatter search metaheuristic

Rough set theory is an effective method to feature selection, which has recently fascinated many researchers. The essence of rough set approach to feature selection is to find a subset of the original features. It is, however, an NP-hard problem finding a minimal subset of the features, and it is necessary to investigate effective and efficient heuristic algorithms. This paper presents a novel rough set approach to feature selection based on scatter search metaheuristic. The proposed method, called scatter search rough set attribute reduction （SSAR）, is illustrated by 13 well known datasets from UCI machine learning repository. The proposed heuristic strategy is compared with typical attribute reduction methods including genetic algorithm, ant colony, simulated annealing, and Tabu search. Computational results demonstrate that our algorithm can provide efficient solution to find a minimal subset of the features and show promising and competitive performance on the considered datasets.     

Fault-tolerant control of linear uncertain systems using H∞ robust predictive control

The robust fault-tolerant control problem of linear uncertain systems is studied. It is shown that a solution for this problem can be obtained from a H∞ robust predictive controller （RMPC） by the method of linear matrix inequality （LMI）. This approach has the advantages of both H∞ control and MPC： the robustness and ability to handle constraints explicitly. The robust closed-loop stability of the linear uncertain system with input and output constraints is proven under an actuator and sensor faults condition. Finally, satisfactory results of simulation experiments verify the validity of this algorithm.     

A line search filter secant method for nonlinear equality constrained optimization

<正> This paper formulates and analyzes a line search method for general nonlinear equalityconstrained optimization based on filter methods for step acceptance and secant methods for searchdirection.The feature of the new algorithm is that the secant algorithm is used to produce a searchdirection,a backtracking line search procedure is used to generate step size,some filtered rules areused to determine step acceptance,second order correction technique is used to reduce infeasibility andovercome the Maratos effect.Global convergence properties of this method are analyzed:under mildassumptions it is showed that every limit point of the sequence of iterates generated by the algorithmis feasible,and that there exists at least one limit point that is a stationary point for the problem.Moreover,it is also established that the Maratos effect can be overcome in our new approach by addingsecond order correction steps so that fast local superlinear convergence to a second order sufficient localsolution is achieved.Finally,the results of numerical experiments are reported to show the effectivenessof the line search filter secant method.     

Improved genetic algorithm for nonlinear programming problems

An improved genetic algorithm(IGA) based on a novel selection strategy to handle nonlinear programming problems is proposed.Each individual in selection process is represented as a three-dimensional feature vector which is composed of objective function value,the degree of constraints violations and the number of constraints violations.It is easy to distinguish excellent individuals from general individuals by using an individuals’ feature vector.Additionally,a local search(LS) process is incorporated into selection operation so as to find feasible solutions located in the neighboring areas of some infeasible solutions.The combination of IGA and LS should offer the advantage of both the quality of solutions and diversity of solutions.Experimental results over a set of benchmark problems demonstrate that IGA has better performance than other algorithms.     

QUALITATIVE ANALYSIS FOR A THIRD-ORDER DIFFERENTIAL EQUATION IN A MODEL OF CHEMICAL SYSTEMS

In this paper a mathematical model of chemical systems is investigated.We present the conditions for the existence and local stability of the steady statesand the periodic solution of the Hopf type.Specifically,we show by using an ana-lytical method that there may exist two or four Hopf bifurcation points separatedat a finite distance from each other;at the same time,a technique for studying theHopf bifurcation value is given.     

Exponential distribution-based genetic algorithm for solving mixed-integer bilevel programming problems

Two classes of mixed-integer nonlinear bilevel programming problems are discussed. One is that the follower＇s functions are separable with respect to the follower＇s variables, and the other is that the follower＇s functions are convex if the follower＇s variables are not restricted to integers. A genetic algorithm based on an exponential distribution is proposed for the aforementioned problems. First, for each fixed leader＇s variable x, it is proved that the optimal solution y of the follower＇s mixed-integer programming can be obtained by solving associated relaxed problems, and according to the convexity of the functions involved, a simplified branch and bound approach is given to solve the follower＇s programming for the second class of problems. Furthermore, based on an exponential distribution with a parameter λ, a new crossover operator is designed in which the best individuals are used to generate better offspring of crossover. The simulation results illustrate that the proposed algorithm is efficient and robust.     

A Heuristic Algorithm for QoS Multicast Routing

In recent years, QoS multicast routing has continued to be a very important research topic in the areas of networks. This paper presents a heuristic algorithm for the QoS multicast routing (HAQMR). This heuristic algorithm deals with delay and bandwidth constraints and has low cost. The HAQMR attempts to significantly reduce the overhead for constructing a multicast tree, the proof for correctness of the HAQMR is given, and the performance of the HAQMR is evaluated by simulations. The study shows that HAQMR provides an available approach to QoS multicast routing.     

带振荡策略的启发式算法求解一类新型分配问题

提出了一种新型的分配问题,该问题来源于钢铁企业中的板坯优化管理.与一般分配问题相比,该问题在将物品分配给背包时,除了需满足背包的容量限制外,还需满足流向限制.此问题可归结为 一般分配问题,因此为NP难问题.针对该问题,提出了带有振荡策略和长期表的启发式算法求解.振荡策略使局部搜索算法在可行区域和不可行区域间振荡,以获得更好的近优解;其次,在算法中引入了禁忌搜索的长期表,根据频率鼓励物品的多样性移动,提高算法的分散搜索能力.为验证算法有效性, 对随机产生的23种规模的数据进行了实验.实验结果表明：对于小规模数据,算法结果与最优解的最大偏差为0.55{\%};在大规模情况下,算法能在快速的时间内获得问题的近优解.     

Real coded genetic algorithm for stochastic hydrothermal generation scheduling

The intent of this paper is to schedule short-term hydrothermal system probabilistically considering stochastic operating cost curves for thermal power generation units and uncertainties in load demand and reservoir water inflows. Therefore, the stochastic multi-objective hydrothermal generation scheduling problem is formulated with explicit recognition of uncertainties in the system production cost coefficients and system load, which are treated as random variable. Fuzzy methodology has been exploited for solving a decision making problem involving multiplicity of objectives and selection criterion for best compromised solution. A real-coded genetic algorithm with arithmetic-average-bound-blend crossover and wavelet mutation operator is applied to solve short-term variable-head hydrothermal scheduling problem. Initial feasible solution has been obtained by implementing the random heuristic search. The search is performed within the operating generation limits. Equality constraints that satisfy the demand during each time interval are considered by introducing a slack thermal generating unit for each time interval. Whereas the equality constraint which satisfies the consumption of available water to its full extent for the whole scheduling period is considered by introducing slack hydro generating unit for a particular time interval. Operating limit violation by slack hydro and slack thermal generating unit is taken care using exterior penalty method. The effectiveness of the proposed method is demonstrated on two sample systems.     

导引式局部搜索在一类过度约束VRP中的应用

针对一类带时间窗口和容量约束的车辆路线问题(VRP),给出了在过度约束即不存在满足所有约束的可行解的情况下,能够最小化约束违反成本的一种新颖的导引式局部搜索(GLS)算法。该算法通过不断动态修改原问题的目标函数,既保留了局部搜索算法的高效率,又有效克服了局部极小解的局限性,因而能够较快地返回一个满意解。求解示例表明,该算法在求解此类问题时,性能要优于常用的禁忌搜索算法。     

单机订单接受与加工调度问题的拉格朗日松弛算法

针对不同类型订单加工切换时机器需要准备时间的实际生产情况,研究了单机订单接受与加工调度优化决策问题,旨在最大化企业净收益。鉴于研究问题的强NP难属性,设计了基于拉格朗日松弛理论的启发式算法。首先,该算法通过加入相邻订单相异性约束以提高松弛解质量;其次,应用动态规划递推公式求解拉格朗日松弛问题;最后,利用问题的优化性质并基于贪婪规则构造原问题可行解。不同规模问题的实验结果表明,该算法能在合理计算时间内得到满意的近优解。     

求解N-车探险问题的离散水波优化算法

N-车探险问题是一类NP-hard离散优化问题，针对该问题，首次提出一种融合局部搜索的离散水波优化算法。结合该问题等价于置换排序的特性，设计基于置换序列的编码方式；利用反转、移动、交换等操作重新定义传播、折射和碎浪算子；开发基于插入邻域的局部搜索策略，以增强水波优化算法的局部搜索能力。最后，利用实验设计探讨关键参数对算法性能的影响。基于14个标准问题的测试结果表明：所提方法的寻优精度、稳定性等整体优于标准水波优化算法、粒子群算法、烟花算法和启发式算法H1~H4；与离散水波优化算法相比，基于禁忌搜索的变邻域搜索算法用至少66.6倍的计算时间得到了最大相对偏差比为0.017的寻优精度。结果表明，离散水波优化算法能在较短时间内获得较满意的解。     

A Sensitivity-Based Heuristic Search for Constrained Optimization in Complex Systems

1.INTRODUCTIONThealgorithmforconstrainedoptimizationincomplexsystemscanbedividedintotwoclasses:exactandheuristicmethods.Theexactmethods,whicharepartlysummarizedbyTitanetal.[1],havecomputationalrequiremeatsthatgrowexponentiajlywiththesizeoftheproblem.AlthoughheuristicmethodshavemodestcomputationalrequirementsandareeasytoAnplemellt,theyaregenerallyforredundancyallocation[2-4].2.S~EMENTOFProBLEM2.1NotationN:nUmberofcomponents;M:numberofconstraints;Rs:systemreliability;Rj:thereliabili…     

一种求解连续空间优化问题的改进蚁群算法

蚁群算法是近几年优化领域中新出现的一种启发式仿生类并行智能进化算法,该算法采用分布式并行计算和正反馈机制,易于与其它方法结合,目前虽然已经在离散空间优化领域中得到了广泛应用,但是在求解连续空间优化问题方面的研究相对较少。在介绍基本蚁群算法机制原理和数学模型的基础上,提出了一种用于求解连续空间优化问题的改进蚁群算法。将连续空间优化问题的解向量分解成有限个网格,同时构造了一个与蚁群转移概率相关的评价函数,并借助相遇搜索策略对蚁群算法进行了改进,将各条寻优路径上可能的残留信息素数量限制在一个最大最小区间,以提高改进后蚁群算法的全局收敛性能。仿真实验表明,提出的改进蚁群算法较文献[11]所提出的自适应蚁群算法能更快地找到连续空间优化问题更优良的全局解,从而为蚁群算法求解这类问题提供了一条可行有效的新途径。     

局部通信条件下多无人机协同搜索方法

针对复杂场景中障碍物、电磁干扰等因素造成的无人机(unmanned aerial vehicle, UAV)编队部分通信链路不可达问题, 提出局部通信条件下的协同搜索(cooperative search under local communication, CSLC)方法。首先, 根据各UAV的实时位置计算当前时刻编队通信拓扑关系, 建立UAV编队的局部互通网络。在此基础上, 综合考虑UAV通信能力和编队协同目标搜索能力, 构建基于通信链路稳定收益和协同编队收益的协同搜索模型。最后, 设定多UAV编队所需的安全距离和最大运动速率的约束条件, 保证模型能够得到最优路径可行解, 提高多UAV协同搜索效率。实验结果表明, 与现有的目标搜索方法相比, CSLC方法在保证协同搜索路径可行性的同时, 提升了多UAV协同搜索的能力。     

油品配送车辆路径问题的交互式求解方法

油品配送车辆路径问题是一个多车场、多仓库、多商品、多舱位、多车型、有前序约束和时间窗,综合车辆分派、订单配载以及路径编排等决策的车辆路径问题.以两阶段启发式算法为基础,给出了求解该问题的人机交互式求解方法,即交互进行基于当前解的人工修改和启发式算法的寻优.其中包括了对初始解、搜索邻域和目标函数的人工修改,相应操作分别为修改解、局部固定解和调整惩罚乘子.     

切向加速度与弦误差约束的CNC系统时间最优轨迹规划

针对计算机数控(CNC)系统给定参数化路径, 给出了一种求解时间最优轨迹规划问题的凸优化方法. 轨迹规划问题考虑切向加速度约束与弦误差约束. 通过建立两种约束下的状态容许空间, 分析约束对时间最优轨迹的影响. 通过非线性变量代换, 时间最优轨迹规划问题被表述为一个与时间无关的凸最优控制问题. 基于控制向量参数化(CVP)方法, 问题被进一步转化为易于求解的凸优化问题. 以路径参数对时间的二阶导数(参数加速度)为优化变量, 序列二次规划(SQP)方法获得问题数值解. 文末通过求解两个测试路径的时间最优轨迹规划问题, 验证方法的有效性.