6,794 research outputs found
Improving Performance in Combinatorial Optimisation Using Averaging and Clustering
No full textIn a recent paper an algorithm for solving MAX-SAT was proposed which worked by clustering good solutions and restarting the search from the closest feasible solutions. This was shown to be an extremely effective search strategy, substantially out-performing traditional optimisation techniques. In this paper we extend those ideas to a second classic NP-Hard problem, namely Vertex Cover. Again the algorithm appears to provide an advantage over more established search algorithms, although it shows different characteristics to MAX-SAT. We argue this is due to the different large-scale landscape structure of the two problems
Analysis of the fitness landscape for the class of combinatorial optimisation problems
No full textAnatomy of the fitness landscape for a group of well known combinatorial optimisation problems is studied in this research and the similarities and the differences between their landscapes are pointed out. In this research we target the analysis of the fitness landscape for MAX-SAT, Graph-Colouring, Travelling Salesman and Quadratic Assignment problems. Belonging to the class of NP-Hard problems, all these problems become exponentially harder as the problem size grows. We study a group of properties of the fitness landscape for these problems and show what properties are shared by different problems and what properties are different. The properties we investigate here include the time it takes for a local search algorithm to find a local optimum, the number of local and global optima, distance between local and global optima, expected cost of found optima, probability of reaching a global optimum and the cost of the best configuration in the search space. The relationship between these properties and the system size and other parameters of the problems are studied, and it is shown how these properties are shared or differ in different problems. We also study the long-range correlation within the search space, including the expected cost in the Hamming sphere around the local and global optima, the basin of attraction of the local and global optima and the probability of finding a local optimum as a function of its cost. We believe these information provide good insight for algorithm designers
Learning the large-scale structure of the max-sat landscape using populations
No full textA new algorithm for solving MAX-SAT problems is introduced which clusters good solutions, and restarts the search from the closest feasible solution to the centroid of each cluster. This is shown to be highly efficient for finding good solutions of large MAX-SAT problems. We argue that this success is due to the population learning the large-scale structure of the fitness landscape. Systematic studies of the landscape are presented to support this hypothesis. In addition, a number of other strategies are tested to rule out other possible explanations of the success. Preliminary results are shown indicating that extensions of the proposed algorithm can give similar improvements on other hard optimisation problems
Recommended from our members
Emmett L. Bennett, Jr. Offprint Collection
No full textThe scholarly library of Emmett L. Bennett, Jr. compiled in the course of his Editorship of the journal Nestor (founded in 1957). The collection includes scholarly publications (offprints) and manuscripts sent by prospective authors to Dr. Bennett. Includes a Finding Aid (PDF and Word) and Catalog (an Excel document for each of two record groups: offprints collected up to 1995, and offprints collected from 1995-2011). Both the Finding Aid and Catalog are provided to facilitate researchers' searches for offprints by author, title, journal, year, and subject.Classic
Novel Heuristics for Coalition Structure Generation in Multi-Agent Systems
No full textA coalition is a set of self-interested agents that agree to cooperate for achieving a set of goals. Coalition formation is an active area of research in multi-agent systems nowadays. Central to this endeavour is the problem of determining which of the many possible coalitions to form in order to achieve some goal, which is called coalition structure generation. Coalition structure generation problem is extremely challenging due to the number of possible solutions that need to be examined, which grows exponentially with the number of agents involved. Generally, agents would enumerate all possible coalitions, store them in memory, and then try to construct the coalition structure that maximizes the sum of the values of the coalitions. However, this is not feasible when we have a large number of agents, and other constraints on execution time, and memory. Hence, there is a need to develop an algorithm that can generate solutions rapidly for large number of agents while providing bounds on the value of solution as well. With this in mind, we propose two new heuristics, namely LocalSearch and GreedySearch, for generating the coalition structure, which satisfy these properties. We empirically show that these heuristics are able to return ‘good-enough’ solutions in very short time. Furthermore, they enhance the performance of state of the art algorithm, IP (proposed by [12]) in terms of increased lower bound, anytime property, and solution quality. Furthermore, we implemented different heuristics for selecting a sub-space in the IP algorithm and show how the time required to find a good-enough solution depends on the selection of a sub-space in the IP algorithm
Building Switching Hybrid Recommender System Using Machine Learning Classifiers and Collaborative Filtering
No full textRecommender systems apply machine learning and data mining techniques for filtering unseen information and can predict whether a user would like a given resource. To date a number of recommendation algorithms have been proposed, where collaborative filtering and content-based filtering are the two most famous and adopted recommendation techniques. Collaborative filtering recommender systems recommend items by identifying other users with similar taste and use their opinions for recommendation; whereas content-based recommender systems recommend items based on the content information of the items. Moreover, machine learning classifiers can be used for recommendation by training them on content information. These systems suffer from scalability, data sparsity, over specialization, and cold-start problems resulting in poor quality recommendations and reduced coverage. Hybrid recommender systems combine individual systems to avoid certain aforementioned limitations of these systems. In this paper, we proposed unique generalized switching hybrid recommendation algorithms that combine machine learning classifiers with the collaborative filtering recommender systems. Experimental results on two different data sets, show that the proposed algorithms are scalable and provide better performance—in terms of accuracy and coverage—than other algorithms while at the same time eliminate some recorded problems with the recommender systems
Novel Significance Weighting Schemes for Collaborative Filtering: Generating Improved Recommendations in Sparse Environments
No full textRecommender systems apply machine learning and data mining techniques for filtering unseen information and can predict whether a user would like a given resource. To date, a number of recommender system algorithms have been proposed, where collaborative filtering is the most famous and adopted recommendation algorithm. Collaborative filtering recommender systems recommend items by identifying other similar users, in case of user-based collaborative filtering, or similar items, in case of item-based collaborative filtering. Significance weighting schemes assign different weights to neighbouring users/items found against an active user/item. Several significance weighting schemes have been proposed [1], [2], [3], [4]. In this paper, we claim that these proposed schemes are flawed by the fact that they can not be applied to general recommender system datasets. We provide the correct generalized significance weighting schemes using different novel heuristics, and by extensive experimental results on three different data sets, show how significance weighting schemes affect the performance of a recommender system. Furthermore, we claim that the conventional weighted sum prediction formula used in item-based [5] collaborative filtering is not correct for very sparse datasets. We provide the correct prediction formula and empirically evaluate it
Incremental Kernel Mapping Algorithms for Scalable Recommender Systems
No full textRecommender systems apply machine learning techniques for filtering unseen information and can predict whether a user would like a given item. Kernel Mapping Recommender (KMR)system algorithms have been proposed, which offer state-of-the-art performance. One potential drawback of the KMR algorithms is that the training is done in one step and hence they cannot accommodate the incremental update with the arrival of new data making them unsuitable for the dynamic environments. From this line of research, we propose a new heuristic, which can build the model incrementally without retraining the whole model from scratch when new data (item or user) are added to the recommender system dataset. Furthermore, we proposed a novel perceptron type algorithm, which is a fast incremental algorithm for building the model that maintains a good level of accuracy and scales well with the data. We show empirically over two datasets that the proposed algorithms give quite accurate results while providing significant computation savings
Fulfilling the needs of gray-sheep users in recommender systems, a clustering solution
No full textRecommender systems apply data mining techniques for filtering unseen information and can predict whether a user would like a given item. This paper focuses on graysheep users problem responsible for the increased error rate in collaborative filtering based recommender systems algorithms. The main contribution of this paper lies in showing that (1) the presence of gray-sheep users can affect the performance— accuracy and coverage—of collaborative filtering based algorithms, depending on the data sparsity and distribution; (2) graysheep users can be identified using clustering algorithms in offline fashion, where the similarity threshold to isolate these users from the rest of clusters can be found empirically; (3) contentbased profile of gray-sheep users can be used for making accurate recommendations. The effectiveness of the proposed algorithm is tested on the MovieLens dataset and community of movie fans in the FilmTrust Website, using mean absolute error, receiver operating characteristic sensitivity, and coverage
Immaculate catalogues, indexes and monsters too…: David E. Bennett reports on the three-day residential CILIP Cataloguing and Indexing Group Annual Conference, University of East Anglia, Norwich, UK, 13-15 September 2006.
No full text- …
