Using Dynamic Geometry Software to Add Contrast to Geometric Situations – A Case Study

There is no lack of suggestions concerning how Dynamic Geometry Software (DGS) may support heuristic approaches to problem solving. However, uses of DGS are often limited purely to a verifying role, in the sense that students are expected to vary or confirm empirically at the computer geometric data which are more or less given. By contrast, it seems worthwhile to seek other uses of DGS which go beyond mere confirmation so that the geometric situation is recognised in its particularity. This paper provides a case study that emerged from a project in which DGS formed an integral part of the pedagogical arrangement. The study is intended to show how the contrasting power of DGS might be utilised in a guided discovery setting.This revised version was published online in September 2005 with corrections to the Cover Date.     

Uniform machine scheduling with machine available constraints

1.IntroductionIntheclassicalparallelmachineschedulingareaweassumethatmachinesarealwaysavailable.However,aspointedin[1],inrealindustrysettingsthisassumptionmaynotbetrue.Forexample,machinesmaynotalwaysbeavailablebecauseoftheirpreventivemaintenanceduringtheschedulingperiod.Thatistosay,eachmachineiisunavailablefromsibuntilrib(05sib5rib),where0SkSm,withmbeingthenumberofunavailabilityperiodsformachineiduringtheplanninghorizon.Inotherwords,somepapersstatethatmachinesareavailableintimewindows,whichi…     

Integrating Interval Estimates of Global Optima and Local Search Methods for Combinatorial Optimization Problems

The problem of estimating the global optimal values of intractable combinatorial optimization problems is of interest to researchers developing and evaluating heuristics for these problems. In this paper we present a method for combining statistical optimum prediction techniques with local search methods such as simulated annealing and tabu search and illustrate the approach on a single machine scheduling problem. Computational experiments show that the approach yields useful estimates of optimal values with very reasonable computational effort.     

烷基苯酚类化合物的气相色谱保留值与其结构参数的定量关系

计算了44个烷基苯酚类化合物的组成、拓扑、几何、静电和量子化学等结构参数,运用启发式方法对这些结构参数进行筛选,得到了含3个变量的化合物的定量结构与色谱保留值的线性关系模型,同时以这3个变量作为支持向量机模型的输入变量建立非线性回归模型。两种方法的相关系数(R2 )分别为0.98和0.92,相应的均方根误差分别是0.99和2.77。通过对两种模型的稳定性和预测能力的比较,发现线性模型能够更好地反映烷基苯酚的气相色谱保留值与其结构参数之间的定量关系。在已知烷基苯酚类化合物结构参数的情况下,线性回归模型更有助于它们的色谱分析。     

面向靠桥率及道口冲突率的航班-机位指派问题优化模型及其启发式算法研究

在给定航班时刻表条件下,对于进出港航班的机位分配,除了必须满足航班、飞机和机位之间的技术性要求之外,还要考虑尽量提高整个机场的机位利用率,且方便旅客出入港及时、安全和便捷.文章以飞机机型、所属航空公司、客运/货运航班、国内/国际航班等匹配条件为约束条件,以航班-机位分配完成率、靠桥率、道口非冲突率为目标,建立了一个航班...     

EGFAFS: A Novel Feature Selection Algorithm Based on Explosion Gravitation Field Algorithm

Feature selection (FS) is a vital step in data mining and machine learning, especially for analyzing the data in high-dimensional feature space. Gene expression data usually consist of a few samples characterized by high-dimensional feature space. As a result, they are not suitable to be processed by simple methods, such as the filter-based method. In this study, we propose a novel feature selection algorithm based on the Explosion Gravitation Field Algorithm, called EGFAFS. To reduce the dimensions of the feature space to acceptable dimensions, we constructed a recommended feature pool by a series of Random Forests based on the Gini index. Furthermore, by paying more attention to the features in the recommended feature pool, we can find the best subset more efficiently. To verify the performance of EGFAFS for FS, we tested EGFAFS on eight gene expression datasets compared with four heuristic-based FS methods (GA, PSO, SA, and DE) and four other FS methods (Boruta, HSICLasso, DNN-FS, and EGSG). The results show that EGFAFS has better performance for FS on gene expression data in terms of evaluation metrics, having more than the other eight FS algorithms. The genes selected by EGFAGS play an essential role in the differential co-expression network and some biological functions further demonstrate the success of EGFAFS for solving FS problems on gene expression data.     

Gaussian-Based Adaptive Fish Migration Optimization Applied to Optimization Localization Error of Mobile Sensor Networks

Location information is the primary feature of wireless sensor networks, and it is more critical for Mobile Wireless Sensor Networks (MWSN) to monitor specific targets. How to improve the localization accuracy is a challenging problem for researchers. In this paper, the Gaussian probability distribution model is applied to randomize the individual during the migration of the Adaptive Fish Migration Optimization (AFMO) algorithm. The performance of the novel algorithm is verified by the CEC 2013 test suit, and the result is compared with other famous heuristic algorithms. Compared to other well-known heuristics, the new algorithm achieves the best results in almost 21 of all 28 test functions. In addition, the novel algorithm significantly reduces the localization error of MWSN, the simulation results show that the accuracy of the new algorithm is more than 5% higher than that of other heuristic algorithms in terms of mobile sensor node positioning, and more than 100% higher than that without the heuristic algorithm.     

Making use of social prototypes: From fuzzy concepts to firm decisions

Evidence suggestive of the ‘fuzzy’ structure of many natural language (as opposed to scientific) categories is reviewed. Examples are drawn from categorization schemes for objects, such as cars, fruit or tables, as well as for people, such as extroverts, hippies and ‘fraternity types’. It is argued that despite the fuzziness of natural categories, there is orderliness and utility to these concepts, as well. Specifically, natural categories are organized around prototypes, representative category members, which serve as reference points for the category. The identification of category members involves a prototype-matching process. Prototypes about ‘kinds of people’ can be very useful in decisions about people with whom to affiliate and places in which to live. This process was illustrated by reference to a case analysis of students' preferences for university housing. It was concluded that natural categories may well be fuzzy, but they are far from being dispensible.     

Order statistics applications to queueing and scheduling problems

We prove several basic combinatorial identities and use them in two applications: the queue inference engine (QIE) and earliest due date rule (EDD) scheduling. Larson (1990) introduced the QIE. His objective was to deduce the behavior of a multiserver queueing system without observing the queue. With only a Poisson arrival assumption, he analyzed the performance during a busy period. Such a period starts once all servers are busy with the queue empty, and it ends as soon as a server becomes idle. We generalize the standard order statistics result for Poisson processes, and show how to sample a busy period in the M/M/c system. We derive simple expressions for the variance of the total waiting time in the M/M/c and M/D/1 queues given that n Poisson arrivals and departures occur during a busy period. We also perform a probabilistic analysis of the EDD for a one-machine scheduling problem with earliness and tardiness penalties. The schedule is without preemption and with no inserted idle time. The jobs are independent and each may have a different due date. For large n, we show that the variance of the total penalty costs of the EDD is linear in n. The mean of the total penalty costs of the EDD is known to be proportional to the square root of n (see Harel (1993)). This revised version was published online in June 2006 with corrections to the Cover Date.     

Local Search Algorithms for the Bin Packing Problem and Their Relationships to Various Construction Heuristics

The tradeoff between the speed and quality of the solutions obtained by various construction and local search algorithms for the elementary bin packing problem (BPP) are analyzed to obtain useful information for designing algorithms for real-world problems that can be modeled as BPPs. On the basis of intensive computational experiments, we observe that the framework of a solution (i.e., a part of a solution consisting of large items or items with tight constraints) should be constructed in the early stages of a local search. New local search algorithms are proposed as empirical support for the observation.