多无人机协同任务策略优化

从研究多无人机协同任务的系统资源分配、任务分配、航线规划、轨迹优化等问题入手,建立了多基地多无人机协同侦察模型.针对问题,首先利用"栅格化聚拢"的思想对目标点进行过滤优化,进而对目标群和无人机基地进行了任务分配,而后结合蚁群算法、贪心算法、最短路径算法等思想,通过Matlab平台,计算出能够让无人机停留在雷达探测区域总时间最少的最优策略.     

一类求解非线性等式和不等式约束优化问题的区间算法

在Moore二分法的基础上,通过构造的区间列L中标志矢量R的分量取值来删除部分不满足约束条件的区域,将非线性约束优化问题转化为初始域子域上的无约束优化问题,该算法可利用极大熵方法求解多目标优化问题,理论分析和数值结果均表明,这种算法是稳定且可靠的.     

卫星数传接收规划模型与算法研究

作为对地观测卫星任务执行的两个重要阶段之一,数传接收的规划任务是一个具有多时间窗口、多优化目标和多资源约束的NP-Hard优化问题。中继星的引入为数据全天候近实时传输提供可能,同时也为数传规划提出新的问题。本文主要完成两项工作:第一,建立风险控制的卫星数传接收规划模型;第二,阐述基于遗传禁忌的模型求解方法,进一步采用分布式并行求解策略,改善了求解算法的收敛速度和鲁棒性。最后,通过STK提供基础仿真数据,验证了本文规划模型和求解算法的有效性。     

高可扩展区域分解算法及其在流体模拟和优化问题中的应用

本文介绍一套求解复杂流体模拟和优化控制问题的高可扩展并行算法.该算法基于非结构化网格,结合了加稳定化项的有限元空间离散方法、全隐的时间离散格式、多物理场全耦合的求解算法、区域分解算法及求解非线性系统的Newton-Krylov-Schwarz算法等多套先进算法.利用该算法,本文对多个实际工程应用中流体模拟和优化设计问题进行了测试,数值结果显示,该算法对本文研究的几类问题,具有很好的收敛性和并行可扩展性,当使用8192个处理器核求解规模超过两千万个网格单元的问题时,仍然具有超过40%的并行效率.     

承继关系下多资源受限多项目选择计划模型及其智能决策方案

综合多资源、项目权重和承继因素,以充分利用资源和均衡分配计划期内资源为目标,提出含多重资源约束的多项目选择计划混合优化决策模型;进而,基于体液免疫应答中B细胞应答抗原的运行机制和机理,提取简化的应答框架并结合资源约束设计算子模块,获得寻求多资源受限多项目选择计划问题的最优决策方案的隐并行免疫算法;数值实验比较结果显示该算法能获得满足资源限制的最佳决策方案,论证了该决策模型的合理性和应用潜力.     

基于区域分解的CRS算法

本文针对带有盒子约束的非线性规划问题提出一种算法，该算法把解空间分成几个区域，根据每个区域上解的信息定义其选择概率，再根据轮盘赌选择法选择某个区域，在选择的区域上进行CRS（Control Random Search）算法操作。该方法能够缩小搜索空间，从而提高算法的搜索能力及算法的收敛速度，特别是在算法的后期效果更加明显。最后把提出的算法应用到两个典型的函数优化问题中，数值结果表明，算法是可行的、有效的。     

采用复合规则约束的多种群自适应进化算法

针对种群固定的进化算法容易使个体集中分布在局部区域,不利于处理大尺度空间和多峰类型的优化问题,提出了一种多种群分布并且动态变化的种群自适应进化算法.采用Logistic模型模拟多个种群在有限资源下的竞争关系,设计了稳定性规则、熵规则和精英规则以确定不同种群的Logistic模型参数,从而控制种群数量的变化.同时,算法引入了算术内插和外插两种交叉算子,使得各个种群依据自身类型来缩小或扩展搜索空间.此外,算法还通过周期性的调整规则重新构建种群和分配资源.通过5组大尺度和多峰优化问题的测试结果表明,所提的种群自适应方法能够有效改善算法的寻优性能,在达到同等优化水平时所提算法消耗的函数调用次数为对比算法的61.08%～91.55%.     

基于粒子群算法的大型网络计划资源优化

现有求解网络计划资源优化的方法中,解析法不能解决大型复杂网络优化问题,启发式方法过多依赖具体问题、求解效率低,遗传算法生成新一代优化解种群依据的三个算子的实现参数选择,大部分依靠经验并严重影响解的品质,粒子群算法存在大型网络计划资源优化计算量过大和缺少大型网络计划资源优化算例问题.借助设计网络计划时间参数的计算机算法、建立评价函数、设计进化方程等基础工作,选择与工作开始时间相关的变量作为粒子空间位置,用蒙特卡洛方法和限制条件优化初始粒子群,设置可行解范围,用二维动态数组解决大型网络计划资源优化运行image超限问题,通过粒子群算法进化,寻求大型网络计划资源优化解,算例表明基于粒子群算法的大型网络计划资源优化效果明显,粒子群算法参数分析表明:粒子群算法的参数会影响网络计划资源优化结果,而且初始粒子群限制条件和优化目标设置的影响程度较大.     

两个约束条件下多产品报童问题的求解方法研究

对两个约束条件下多产品报童问题的求解方法进行研究。首先分析了问题的结构特征,利用对偶问题解空间的四个不同区域对应的最优解具有的不同性质,给出了不同解空间区域的求解思路。然后基于两种资源的边际利益的性质,提出一种二分搜索算法对问题进行求解,并证明了该算法能够得到问题的最优解或者近似最优解,且具有多项式复杂度。最后应用算例说明算法计算效率高,可以在较少的迭代步骤内快速求解两个线性约束下产品数较大的多产品报童问题。     

多星协同观测条件下区域目标的动杰划分方法

针对多星对区域目标的协同观测问题建模,提出了基于卫星观测能力的动态划分方法,划分时能够充分利用卫星的每次过境观测机会,依据不同卫星的遥感器幅宽、侧摆能力以及卫星轨道参数特征,以及偏移参数动态划分区域目标,构造多个候选观测场景,特别适用于运动轨迹、工作模式存在差异的多颗卫星联合观测的情况.仿真实验表明,采用本文的划分方法,能够明显提高多星对区域目标协同观测的效率.     

A hybrid hypercube – Genetic algorithm approach for deploying many emergency response mobile units in an urban network

Emergency response services are critical for modern societies. This paper presents a model and a heuristic solution for the optimal deployment of many emergency response units in an urban transportation network and an application for transit mobile repair units (TMRU) in the city of Athens, Greece. The model considers the stochastic nature of such services, suggesting that a unit may be already engaged, when an incident occurs. The proposed model integrates a queuing model (the hypercube model), a location model and a metaheuristic optimization algorithm (genetic algorithm) for obtaining appropriate unit locations in a two-step approach. In the first step, the service area is partitioned into sub-areas (called superdistricts) while, in parallel, necessary number of units is determined for each superdistrict. An approximate solution to the symmetric hypercube model with spatially homogeneous demand is developed. A Genetic Algorithm is combined with the approximate hypercube model for obtaining best superdistricts and associated unit numbers. With both of the above requirements defined in step one, the second step proceeds in the optimal deployment of units within each superdistrict.     

Robust optimization for relief logistics planning under uncertainties in demand and transportation time

Emergency logistics is an essential component of post-disaster relief campaigns. However, there are always various uncertainties when making decisions related to planning and implementing post-disaster relief logistics. Considering the particular environmental conditions during post-disaster relief after a catastrophic earthquake in a mountainous area, this paper proposes a stochastic model for post-disaster relief logistics to guide the tactical design for mobilizing relief supply levels, planning initial helicopter deployments, and creating transportation plans within the disaster region, given the uncertainties in demand and transportation time. We then introduce a robust optimization approach to cope with these uncertainties and deduce the robust counterpart of the proposed stochastic model. A numerical example based on disaster logistics during the Great Sichuan Earthquake demonstrates that the model can help post-disaster managers to determine the initial deployments of emergency resources. Sensitivity analyses explore the trade-off between optimization and robustness by varying the robust optimization parameter values.     

An ILP and simulation model to optimize search and rescue helicopter operations

Maritime search and rescue (SAR) operations, conducted for rendering aid to the victims in need of help at sea, play a crucial role in dropping the number of causalities. Therefore, it is of high importance to organize SAR operations properly. In this paper, we compose a hybrid methodology which combines optimization and simulation to allocate SAR helicopters. First, we build an integer linear programming (ILP) model to provide an effective deployment plan and use it as an input to a simulation model which includes constraints that the ILP model cannot tackle. Next, using a rule-based algorithm, we generate alternative solutions and seek better plans that exist in the vicinity of the ILP model solution. We perform our methodology on the historical incident data in the Aegean Sea region. Results show that the hybrid methodology we adopted leads to a more effective utilization of resources than the optimization model alone.     

Single observation adaptive search for discrete and continuous stochastic optimization

Solving a stochastic optimization problem often involves performing repeated noisy function evaluations at points encountered during the algorithm. Recently, a continuous optimization framework for executing a single observation per search point was shown to exhibit a martingale property so that associated estimation errors are guaranteed to converge to zero. We generalize this martingale single observation approach to problems with mixed discrete–continuous variables. We establish mild regularity conditions for this class of algorithms to converge to a global optimum.     

Performance analysis of distributed solution approaches in simulation-based optimization

Applying computationally expensive simulations in design or process optimization results in long-running solution processes even when using a state-of-the-art distributed algorithm and hardware. Within these simulation-based optimization problems the optimizer has to treat the simulation systems as black-boxes. The distributed solution of this kind of optimization problem demands efficient utilization of resources (i.e. processors) and evaluation of the solution quality. Analyzing the parallel performance is therefore an important task in the development of adequate distributed approaches taking into account the numerical algorithm, its implementation, and the used hardware architecture. In this paper, simulation-based optimization problems are characterized and a distributed solution algorithm is presented. Different performance analysis techniques (e.g. scalability analysis, computational complexity) are discussed and a new approach integrating parallel performance and solution quality is developed. This approach combines a priori and a posteriori techniques and can be applied in early stages of the solution process. The feasibility of the approach is demonstrated by applying it to three different classes of simulation-based optimization problems from groundwater management.     

An improved scheme for accelerating the convergence of the simulated annealing algorithm applied to real world problems

When formulated in mathematical terms, the problem of zoning a protected natural area subject to both box and spatial constraints results in a large combinatorial optimization problem belonging to the NP-hard class. These facts suggest the need to apply a heuristic approach. In this contribution a new proposal to decrease the control parameter, known as temperature, in the simulated annealing algorithm is presented. The strategy is based on that proposed by Lundy and Mees [4], and developed in order to decrease the running time of the algorithm applied to large scale problems. When applied to solving small-size simulated problems, results were indistinguishable from those obtained via an exact, enumerative method. A coarse-scale zoning of Talampaya National Park (Argentina) rendered maps remarkably similar to those produced by subject area experts using a non-quantitative consensus-seeking approach. Results are encouraging and show particular potential for the periodical update of zoning of protected natural areas. Such a capability is crucial for application in developing countries where both human and financial resources are usually scarce but still critical for updating zoning and management plans. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

A derivative-free approach for a simulation-based optimization problem in healthcare

Hospitals have been challenged in recent years to deliver high quality care with limited resources. Given the pressure to contain costs, developing procedures for optimal resource allocation becomes more and more critical in this context. Indeed, under/overutilization of emergency room and ward resources can either compromise a hospital’s ability to provide the best possible care, or result in precious funding going toward underutilized resources. Simulation-based optimization tools then help facilitating the planning and management of hospital services, by maximizing/minimizing some specific indices (e.g. net profit) subject to given clinical and economical constraints. In this work, we develop a simulation-based optimization approach for the resource planning of a specific hospital ward. At each step, we first consider a suitably chosen resource setting and evaluate both efficiency and satisfaction of the restrictions by means of a discrete-event simulation model. Then, taking into account the information obtained by the simulation process, we use a derivative-free optimization algorithm to modify the given setting. We report results for a real-world problem coming from the obstetrics ward of an Italian hospital showing both the effectiveness and the efficiency of the proposed approach.     

Inexact de Novo programming for water resources systems planning

This study presents an interval de Novo programming (IDNP) approach for the design of optimal water-resources-management systems under uncertainty. The model is derived by incorporating the existing interval programming and de Novo programming, allowing uncertainties represented as intervals within the optimization framework. The developed IDNP approach has the advantages in constructing optimal system design via an ideal system by introducing the flexibility toward the available resources in the system constraints. A simple numerical example is introduced to illustrate the IDNP approach. The IDNP is then applied to design an inexact optimal system with budget limit instead of finding the optimum in a given system with fixed resources in a water resources planning case. The results demonstrate that the developed method efficiently produces stable solutions under different objectives. Optimal supplies of good-quality water are obtained in considering different revenue targets of municipal–industrial–agricultural competition under a given budget.     

A mixed integer linear programming model for reliability optimisation in the component deployment problem

Component deployment is a combinatorial optimisation problem in software engineering that aims at finding the best allocation of software components to hardware resources in order to optimise quality attributes, such as reliability. The problem is often constrained because of the limited hardware resources, and the communication network, which may connect only certain resources. Owing to the non-linear nature of the reliability function, current optimisation methods have focused mainly on heuristic or metaheuristic algorithms. These are approximate methods, which find near-optimal solutions in a reasonable amount of time. In this paper, we present a mixed integer linear programming (MILP) formulation of the component deployment problem. We design a set of experiments where we compare the MILP solver to methods previously used to solve this problem. Results show that the MILP solver is efficient in finding feasible solutions even where other methods fail, or prove infeasibility where feasible solutions do not exist.     

Maximizing lifetime of a wireless sensor network via joint optimizing sink placement and sensor-to-sink routing

Wireless sensor networks typically contain hundreds of sensors. The sensors collect data and relay it to sinks through single hop or multiple hop paths. Sink deployment significantly influences the performance of a network. Since the energy capacity of each sensor is limited, optimizing sink deployment and sensor-to-sink routing is crucial. In this paper, this problem is modeled as a mixed integer optimization problem. Then, a novel layer-based diffusion particle swarm optimization method is proposed to solve this large-scaled optimization problem. In particular, two sensor-to-sink binding algorithms are combined as inner layer optimization to evaluate the fitness values of the solutions. Compared to existing methods that the sinks are selected from candidate positions, our method can achieve better performance since they can be placed freely within a geometrical plane. Several numerical examples are used to validate and demonstrate the performance of our method. The reported numerical results show that our method is superior to those existing. Furthermore, our method has good scalability which can be used to deploy a large-scaled sensor network.