Search

The pile bearing capacity is considered as the most essential factor in designing deep foundations. Direct determination of this parameter in site is costly and difficult. Hence, this study presents a new technique of intelligence system based on the adaptive neuro-fuzzy inference system (ANFIS)-group method of data handling (GMDH) optimized by the imperialism competitive algorithm (ICA), ANFIS-GMDH-ICA for forecasting pile bearing capacity. In this advanced structure, the ICA role is to optimize the membership functions obtained by ANFIS-GMDH technique for receiving a higher accuracy level and lower error. To develop this model, the results of 257 high strain dynamic load tests (performed by authors) were considered and used in the analysis. For comparison purposes, ANFIS and GMDH models were selected and built for pile bearing capacity estimation. In terms of model accuracy, the obtained results showed that the newly developed model (i.e., ANFIS-GMDH-ICA) receives more accurate predicted values of pile bearing capacity compared to those obtained by ANFIS and GMDH predictive models. The proposed ANFIS-GMDH-ICA can be utilized as an advanced, applicable and powerful technique in issues related to foundation engineering and its design.

Drilling and blasting operations are one of the most effective techniques for rock removal in mines. However, these operations are associated with some environmental issues such as the problem of toe. This issue has a deep impact on blasting cost where there is a need to conduct secondary blasting due to this problem. Therefore, it is beneficial to predict and subsequently optimize this issue. This study attempts to predict toe resulting from blasting by developing artificial neural network (ANN) and decision tree (DT) techniques. To do this, 100 blasting were considered and collected in the Hawzak limestone mine, Iran. Then, the most effective parameters were considered as model inputs and many models of ANN and DT were developed to predict toe induced by blasting. For comparison purposes, multiple regression (REG) was also applied. Three performance indices were used to evaluate the developed models. Coefficients of determination (R2) of 0.76, 0.83 and 0.91 were obtained for testing datasets using the REG, DT and ANN models, respectively, which indicate that ANN can provide higher performance capacity for prediction of toe induced by blasting. In the optimization phase, imperialism competitive algorithm (ICA), which is a new optimization technique in this field, was applied to determine optimal blasting pattern parameters in order to minimize toe induced by blasting. By developing ICA technique, the amount of toe was reduced from 431 to 288 m3 (49.35%), which shows the excellent ability of ICA in optimizing the minimization of toe that arises from blasting operations.

We present an optimally-competitive algorithm for the problem of maximum online perfect bipartite matching with i.i.d. arrivals. In this problem, we are given a known set of workers, a distribution over job types, and non-negative utility weights for each pair of worker and job types. At each time step, a job is drawn i.i.d. from the distribution over job types. Upon arrival, the job must be irrevocably assigned to a worker and cannot be dropped. The goal is to maximize the expected sum of utilities after all jobs are assigned. We introduce Dispatch, a 0.5-competitive, randomized algorithm. We also prove that 0.5-competitive is the best possible. When a job arrives, Dispatch first selects a “preferred worker” and assigns the job to this worker if it is available. The preferred worker is determined based on an optimal solution to a fractional transportation problem. If the preferred worker is not available, Dispatch randomly selects a worker from the available workers.

As blasting has some environmental constraints, ripping has got more prevalent as a method of breaking ground in both civil and mining engineering applications. A rippability model of a higher applicability is, therefore, needed to appropriately predict the ripping production (Q) prior to carrying out such tests. For the purpose of predicting the results of ripping production that were attained in three sites located in Johor state, Malaysia, the present study applied three hybrid intelligent techniques, i.e., neuro-bee, neuro-imperialism, and neuro-swarm, to predict Q. In fact, the effects of artificial bee colony (ABC), imperialism competitive algorithm (ICA), and particle swarm optimization (PSO) on weights and biases of neural networks were examined in the current research to receive better prediction/evaluation of ripping production. To do this, totally, 74 ripping tests were taken into consideration in the investigated regions and their influential parameters were assessed. Many parametric studies on ABC, ICA, and PSO parameters were conducted, and then, a comparison was done on the obtained results of the predictive hybrid models using several performance indices. As confirmed by the comparative results, the neuro-bee model proposed in this study estimated Q with a higher accuracy than the other hybrid models. The root-mean-square error (RMSE) values of 0.060, 0.076, and 0.094 were obtained for testing the data sets of neuro-bee, neuro-imperialism, and neuro-swarm techniques, respectively. This clearly shows that the newly developed hybrid model was superior to its rival in terms of predicting the ripping production. Furthermore, results of sensitivity analysis showed that weathering zone is the most influential factor on ripping production as compared to other inputs.

In the adversarial edge arrival model for maximum cardinality matching, edges of an unknown graph are revealed one-by-one in an arbitrary order, and should be irrevocably accepted or rejected. Here, the goal of an online algorithm is to maximize the number of accepted edges while maintaining a feasible matching at any point in time. For this model, the standard greedy heuristic is $$\nicefrac {1}{2}$$ -competitive, and on the other hand, no algorithm that outperforms this ratio is currently known, even for very simple graphs. We present a clean Min-Index framework for devising a family of randomized algorithms, and provide a number of positive and negative results in this context. Among these results, we present a $$\nicefrac {5}{9}$$ -competitive algorithm when the underlying graph is a forest, and prove that this ratio is best possible within the Min-Index framework. In addition, we prove a new general upper bound of $$\frac{2}{3+1/\phi ^2}\approx 0.5914$$ on the competitiveness of any algorithm in the edge arrival model. Interestingly, while this result slightly falls short of the currently best $$\frac{1}{1+\ln 2} \approx 0.5906$$ bound by Epstein et al. (Inf Comput 259(1):31–40, 2018), it holds even for an easier model in which vertices along with their adjacent edges arrive online. As a result, we improve on the currently best upper bound of 0.6252 for the latter model, due to Wang and Wong (in: Proceedings of the 42nd ICALP, 2015).

Ground vibration resulting from blasting is one of the most important environmental problems at open-cast mines. Therefore, accurately approximating the blast-induced ground vibration is very significant. By reviewing the previous investigations, many attempts have been done to create the empirical models for estimating ground vibration. Nevertheless, the performance of the empirical models is not good enough. In this research work, a new hybrid model of fuzzy system (FS) designed by imperialistic competitive algorithm (ICA) is proposed for approximating ground vibration resulting from blasting at Miduk copper mine, Iran. For comparison aims, various empirical models were also utilized. Results from different predictor models were compared by using coefficient of multiple determination (R 2), variance account for and root-mean-square error between measured and predicted values of the PPVs. Results prove that the FS–ICA model outperforms the other empirical models in terms of the prediction accuracy. In other words, the FS–ICA model with R 2 of 0.942 can forecast PPV better than the USBM with R 2 of 0.634, Ambraseys–Hendron with R 2 of 0.638, Langefors–Kihlstrom with R 2 of 0.637 and Indian Standard with R 2 of 0.519.

This paper studies an online over-list model of the integrated allocation of berths and quay cranes (QCs) in container terminals with 1-lookahead ability. The objective is to minimize the maximum completion time of container vessels, i.e., the makespan. We focus on two different types of vessels, three berths and a small number of QCs in the hybrid berth layout, with 1-lookahead ability. We propose a $${{(1 + \sqrt{2} )/2}}$$ -competitive algorithm for the case with four cranes, a 5/4-competitive algorithm for the case with five cranes and a 4/3-competitive algorithm for the case with six cranes, respectively. All of the algorithms are proved to be optimal.

In the reordering buffer management problem, a sequence of colored items arrives at a service station to be processed. Each color change between two consecutively processed items generates some cost. A reordering buffer of capacity k items can be used to preprocess the input sequence in order to decrease the number of color changes. The goal is to find a scheduling strategy that, using the reordering buffer, minimizes the number of color changes in the given sequence of items. We consider the problem in the setting of online computation with advice. In this model, the color of an item becomes known only at the time when the item enters the reordering buffer. Additionally, together with each item entering the buffer, we get a fixed number of advice bits, which can be seen as information about the future or as information about an optimal solution (or an approximation thereof) for the whole input sequence. We show that for any $$\varepsilon > 0$$ there is a $$(1+\varepsilon )$$ -competitive algorithm for the problem which uses only a constant (depending on $$\varepsilon $$ ) number of advice bits per input item. This also immediately implies a $$(1+\varepsilon )$$ -approximation algorithm which has $$2^{O(n\log 1/\varepsilon )}$$ running time (this should be compared to the trivial optimal algorithm which has a running time of $$k^{O(n)}$$ ). We complement the above result by presenting a lower bound of $$\varOmega (\log k)$$ bits of advice per request for any 1-competitive algorithm.

The traveling salesman problem (TSP) is one of the most studied combinatorial optimization problems. In this paper, we present the new idea of combining the imperial competitive algorithm with a policy-learning function for solving the TSP problems. All offspring of each country are defined as representing feasible solutions for the TSP. All countries can grow increasingly strong by learning the effective policies of strong countries. Weak countries will generate increasingly excellent offspring by learning the policies of strong countries while retaining the characteristics of their own country. Imitating these policies will enable the weak countries to produce improved offspring; the solutions generated will, therefore, acquire a favorable scheme while maintaining diversity. Finally, experimental results for TSP instances from the TSP library have shown that our proposed algorithm can determine the salesman's tour with more effective performance levels than other known methods.

Differential evolution (DE) is one of the most popular and powerful evolutionary algorithms for the real-parameter global continuous optimization problems. However, how to balance the exploration and exploitation is harder work to the researchers improving the performance of DE. Very often, we catch one and lose another. To overcome this problem, this paper presents a novel DE variant, called heterozygous DE with Taguchi local search (THDE), in which two new proposed methods (i.e., multiple schemes heterozygous evolution and Taguchi local search) are employed, with one as enhanced exploration ability and the other enhanced exploitation ability. The experimental studies have been conducted on 27 well-known test functions, including unimodal, multimodal and shifted test functions. Experimental results have verified the quality and effectiveness of THDE. Comparison with the state-of-the-art DE variants has proved that THDE is a type of new competitive algorithm.

This paper is aimed at presenting a new method on the basis of the colonial competitive algorithm to predict horizontal peak ground acceleration and spectral acceleration. The colonial competitive algorithm was developed over the last few years in an attempt to overcome inherent limitations of traditional optimize method. The proposed method employs the optimization capabilities of the colonial competitive algorithm to determine the coefficients of attenuation relationships of peak ground acceleration and spectral acceleration. This method was applied to an ensemble of earthquake records of two seismic zones, namely Zagros and Alborz-Central Iran. The obtained results clearly reveal that the colonial competitive algorithm can be viewed as a powerful and reliable tool for solving complex optimization problems such as attenuation relationship.

The hierarchical median problem consists of finding a hierarchical assignment function sequence of solutions to the well-known k-median problems with growing cardinality. This sequence is said to be r-competitive if the cost of each solution is at most r times of the optimum cost of median problem with a same cardinality, where r is called the competitive ratio. Previously the best algorithm available for this problem has competitive ratio 20.71. In this paper an improved algorithm is proposed with competitive ratio factor 16.

The high latencies for access to background memory like hard disks or flash memory can be reduced by caching or hidden by prefetching. We consider the problem of scheduling the resulting I/Os when the available fast cache memory is limited and when we have real-time constraints where for each requested data block we are given a time interval during which this block needs to be in main memory. We give a near linear time algorithm for this problem which produces a feasible schedule whenever one exists. Another algorithm additionally minimizes I/Os and still runs in polynomial-time. For the online variant of the problem, we give a competitive algorithm that uses lookahead and augmented disk speed. We show a tight relationship between the amount of lookahead and the speed required to get a competitive algorithm.

Submitted by Manuel Brandão (msa@eu.ipp.pt) on 2014-02-11T13:46:33Z No. of bitstreams: 1 ART_BjornAndersson_2010_CISTER.pdf: 98518 bytes, checksum: e53ad378f139f654a685ea0c48772f07 (MD5) Approved for entry into archive by Ana Rebelo (amsr@isep.ipp.pt) on 2014-02-12T11:10:08Z (GMT) No. of bitstreams: 1 ART_BjornAndersson_2010_CISTER.pdf: 98518 bytes, checksum: e53ad378f139f654a685ea0c48772f07 (MD5) Made available in DSpace on 2014-02-12T11:10:08Z (GMT). No. of bitstreams: 1 ART_BjornAndersson_2010_CISTER.pdf: 98518 bytes, checksum: e53ad378f139f654a685ea0c48772f07 (MD5) Previous issue date: 2010

We use Mayer-Vietoris trees to obtain the multigraded Betti numbers of monomial ideals without computing their minimal free resolutions. This method provides not only a competitive algorithm for such computations but also a new tool for the analysis of the homological structure of monomial ideals. Using Mayer-Vietoris trees we obtain new results for several families of monomial ideals and new proofs of known results for other families.

In the frequency allocation problem, we are given a mobile telephone network, whose geographical coverage area is divided into cells, wherein phone calls are serviced by assigning frequencies to them so that no two calls emanating from the same or neighboring cells are assigned the same frequency. The problem is to use the frequencies efficiently, i.e., minimize the span of frequencies used. The frequency allocation problem can be regarded as a multicoloring problem on a weighted hexagonal graph. In this paper, we give a 1-local asymptotic 4/3-competitive distributed algorithm for multicoloring a triangle-free hexagonal graph, which is a special case of hexagonal graph. Based on this result, we then propose a 1-local asymptotic13/9-competitive algorithm for multicoloring the (general-case) hexagonal graph, thereby improving the previous 1-local 3/2-competitive algorithm.

In the i>number of snacks problem (i>NSP), which was originally proposed by our team, an on-line player is given the task of deciding how many shares of snacks his noshery should prepare each day. The on-line player must make his decision and then finish the preparation before the customers come to his noshery for the snacks; in other words, he must make decision in an on-line fashion. His goal is to minimize the competitive ratio, defined as ∈σ: CA(σ)/COPT(σ), where σ denotes a sequence of numbers of customers, i>COPT(σ) is the cost of satisfying σ by an optimal off-line algorithm, and i>CA(σ) is the cost of satisfying σ by an on-line algorithm. In this paper we give a competitive algorithm for on-line number of snacks problem i>P1, the i>Extreme Numbers Harmonic Algorithm (i>ENHA), with competitive ratio 1+pc(M-m)/(M+m), where i>M and i>m are two extreme numbers of customers over the total period of the game, and i>p is a ratio concerning the cost of the two types of situations, and then prove that this competitive ratio is the best one if an on-line player chooses a fixed number of shares of snacks for any sequence of numbers of customers. We also discuss several variants of the i>NSP and give some results for it. Finally, we propose a conjecture for the on-line i>NSP.

In this paper, based on the Position Maintaining Strategy (PMS for short), on-line scheduling of k-truck problem, which is a generalization of the famous k-server problem, is originally presented by our team. We proposed several competitive algorithms applicable under different conditions for solving the on-line k-truck problem. First, a competitive algorithm with competitive ratio 2k+1/t is given for any t≥1. Following that, if t≥(c+1)/(c-1) holds, then there must exist a (2k-1)-competitive algorithm for k-truck problem, where c is the competitive ratio of the on-line algorithm about the relevant k-server problem. And then a greedy algorithm with competitive ratio 1+λ/t, where lambda is a parameter related to the structure property of a given graph, is given. Finally, competitive algorithms with ratios 1+1/t are given for two special families of graphs.

Nonsystematic search algorithms seem, in general, to be well suited to large-scale problems with many solutions. However, they tend to perform badly for problems with few solutions, and they cannot be used for insoluble problems, since they are incomplete. Here we present a new algorithm, i>learn-SAT, that, although based on nonsystematic search, is complete. Completeness is realized through a process of no-good learning, learning-by-merging. This requires exponential space in the worst case. We show, nevertheless, that i>learn-SAT performs very well on certain SAT problems that are tightly constrained or insoluble. Indeed, its performance generally approximates the best SAT algorithms and does much better at lower clause densities. i>Learn-SAT also maintains much of the efficient performance of nonsystematic search for large-scale problems with many solutions, at least relative to backtrack search algorithms. These results indicate that the burden on memory, imposed by no-good learning, is not generally a problem for i>learn-SAT. This is perhaps surprising in view of previous work. What is even more surprising is the scalability of i>learn-SAT. For some types of problem it scales very much better than the nearest competitive algorithm. There are other types, however, for which this is not the case. The performance profile of i>learn-SAT emerges from an experimental methodology related to the one outlined by Mammen and Hogg in 1997.

We extend the definition of Metrical Task Systems, introduced by Borodin et al. in [4]. In the extended definition, a system is described by the underlying metric space of states ${\cal M}$ as well as a set of allowable tasks ${\cal T}$ . Any request to an algorithm must be a member of ${\cal T}$ . The extension makes the model powerful enough to characterize completely many important on-line problems. We consider methods of designing competitive algorithms given the description of a system $\langle {\cal M}, {\cal T} \rangle$ . In particular, we show that it is PSPACE-hard to determine the behavior of a $c({\cal M},{\cal T})$ -competitive algorithm, where $c({\cal M},{\cal T})$ is the best possible competitive ratio on $\langle {\cal M},{\cal T} \rangle$ . In addition, we show a simple, polynomial-time algorithm for task systems $\langle {\cal U}_n,{\cal T} \rangle$ (where ${\cal U}_n$ is the uniform metric space on n nodes) that achieves a competitive ratio of $O( \log n \cdot c({\cal M},{\cal T}))$ .

We prove upper and lower bounds on the competitiveness of randomized algorithms for the list update problem of Sleator and Tarjan. We give a simple and elegant randomized algorithm that is more competitive than the best previous randomized algorithm due to Irani. Our algorithm uses randomness only during an initialization phase, and from then on runs completely deterministically. It is the first randomized competitive algorithm with this property to beat the deterministic lower bound. We generalize our approach to a model in which access costs are fixed but update costs are scaled by an arbitrary constantd. We prove lower bounds for deterministic list update algorithms and for randomized algorithms against oblivious and adaptive on-line adversaries. In particular, we show that for this problem adaptive on-line and adaptive off-line adversaries are equally powerful.