Nothing Special   »   [go: up one dir, main page]
Next Issue
Volume 12, May
Previous Issue
Volume 12, March
You seem to have javascript disabled. Please note that many of the page functionalities won't work as expected without javascript enabled.
 
 
Search for Articles:
Title / Keyword
Author / Affiliation / Email
Journal
Article Type
 
 
Advanced Search
 
Section
Special Issue
Volume
Issue
Number
Page
 
4.1
1.8
Journals
Algorithms
Volume 12
Issue 4
share announcement

Algorithms, Volume 12, Issue 4 (April 2019) – 21 articles

Cover Story (view full-size image): Quantum annealers such as the D-Wave machines are designed to propose solutions for quadratic unconstrained binary optimization (QUBO) problems by mapping them onto the quantum processing unit. While many NP-hard problems can be easily formulated as binary quadratic optimization problems, such formulations almost always contain constraints which are not allowed in a QUBO, whose embeddings as quadratic penalties have drawbacks such as introducing large coefficients and using too many couplers. In this paper, we propose an alternative approach for implementing constraints based on a combinatorial design and solving mixed-integer linear programming (MILP) problems in order to find better embeddings of constraints of the type ∑xi=k for binary variables xi. Our approach is scalable to any number of variables and uses a linear number of ancillary variables for a fixed k. View this paper.
  • Issues are regarded as officially published after their release is announced to the table of contents alert mailing list.
  • You may sign up for e-mail alerts to receive table of contents of newly released issues.
  • PDF is the official format for papers published in both, html and pdf forms. To view the papers in pdf format, click on the "PDF Full-text" link, and use the free Adobe Reader to open them.
Order results
Result details
Section
Show export options expand_more Show export options expand_less
Select all
Export citation of selected articles as:
15 pages, 332 KiB  
Article
Oriented Coloring on Recursively Defined Digraphs
by Frank Gurski, Dominique Komander and Carolin Rehs
Algorithms 2019, 12(4), 87; https://doi.org/10.3390/a12040087 - 25 Apr 2019
Cited by 9 | Viewed by 4285
Abstract
Coloring is one of the most famous problems in graph theory. The coloring problem on undirected graphs has been well studied, whereas there are very few results for coloring problems on directed graphs. An oriented k-coloring of an oriented graph [...] Read more.
Coloring is one of the most famous problems in graph theory. The coloring problem on undirected graphs has been well studied, whereas there are very few results for coloring problems on directed graphs. An oriented k-coloring of an oriented graph G = ( V , A ) is a partition of the vertex set V into k independent sets such that all the arcs linking two of these subsets have the same direction. The oriented chromatic number of an oriented graph G is the smallest k such that G allows an oriented k-coloring. Deciding whether an acyclic digraph allows an oriented 4-coloring is NP-hard. It follows that finding the chromatic number of an oriented graph is an NP-hard problem, too. This motivates to consider the problem on oriented co-graphs. After giving several characterizations for this graph class, we show a linear time algorithm which computes an optimal oriented coloring for an oriented co-graph. We further prove how the oriented chromatic number can be computed for the disjoint union and order composition from the oriented chromatic number of the involved oriented co-graphs. It turns out that within oriented co-graphs the oriented chromatic number is equal to the length of a longest oriented path plus one. We also show that the graph isomorphism problem on oriented co-graphs can be solved in linear time. Full article
►▼ Show Figures

Figure 1

Figure 1
<p>Special oriented graphs: oriented cycle <math display="inline"><semantics> <mover accent="true"> <msub> <mi>C</mi> <mn>3</mn> </msub> <mo>→</mo> </mover> </semantics></math> and transitive tournament <math display="inline"><semantics> <mover accent="true"> <msub> <mi>T</mi> <mn>3</mn> </msub> <mo>→</mo> </mover> </semantics></math>.</p> Full article ">Figure 2
<p>The eight forbidden induced subdigraphs for directed co-graphs.</p> Full article ">Figure 3
<p>Canonical di-co-tree <span class="html-italic">T</span> for oriented co-graph <span class="html-italic">G</span>.</p> Full article ">
13 pages, 4671 KiB  
Article
Kalman-Filter-Based Tension Control Design for Industrial Roll-to-Roll System
by Hyeongjin Hwang, Jehwon Lee, Sangjune Eum and Kanghyun Nam
Algorithms 2019, 12(4), 86; https://doi.org/10.3390/a12040086 - 24 Apr 2019
Cited by 11 | Viewed by 6461
Abstract
This paper presents a robust and precise tension control method for a roll-to-roll (R2R) system. In R2R processing, robust and precise tension control is very important because improper web tension control leads to deterioration in the quality of web material. However, tension control [...] Read more.
This paper presents a robust and precise tension control method for a roll-to-roll (R2R) system. In R2R processing, robust and precise tension control is very important because improper web tension control leads to deterioration in the quality of web material. However, tension control is not easy because the R2R system has a model variation in which the inertia of the web in roll form is changed and external disturbances caused by web slip and crumpled web. Therefore, a disturbance observer (DOB) was proposed to achieve robustness against model variations and external disturbances. DOB is a robust control method widely used in various fields because of its simple structure and excellent performance. Moreover, the web passes through various process steps to achieve the finished product in the R2R process. Particularly, it is important to track the tension when magnitude of the tension varies during process. Feedforward (FF) controller was applied to minimize the tracking error in the transient section where tension changes. Moreover, the signal processing of a sensor using the Kalman filter (KF) in the R2R system greatly improved control performance. Finally, the effectiveness of the proposed control scheme is discussed using experimental results. Full article
(This article belongs to the Special Issue Algorithms for PID Controller 2019)
►▼ Show Figures

Figure 1

Figure 1
<p>(<b>a</b>) Schematic of a proposed roll-to-roll (R2R system); (<b>b</b>) Schematic of a rewinder system.</p> Full article ">Figure 2
<p>Experimental results of system identification: (<b>a</b>) Empty film; (<b>b</b>) Half film; (<b>c</b>) Full film.</p> Full article ">Figure 3
<p>Kalman filter (KF) structure.</p> Full article ">Figure 4
<p>Results of signal processing.</p> Full article ">Figure 5
<p>Structure of the proposed controller for R2R system.</p> Full article ">Figure 6
<p>Block diagram of proposed control system: (<b>a</b>) Block diagram of the closed-loop control system with multiplicative model uncertainty; (<b>b</b>) Equivalent block diagram.</p> Full article ">Figure 7
<p>Frequency magnitude response for small-gain theorem check.</p> Full article ">Figure 8
<p>Overall control system for R2R system.</p> Full article ">Figure 9
<p>Overall program flow chart for R2R system.</p> Full article ">Figure 10
<p>Experimental results to verify the effectiveness of KF: (<b>a</b>) Reference and measured tension; (<b>b</b>) Tracking errors.</p> Full article ">Figure 11
<p>Tracking error for three different control cases.</p> Full article ">
11 pages, 988 KiB  
Article
Forecasting Economy-Related Data Utilizing Weight-Constrained Recurrent Neural Networks
by Ioannis E. Livieris
Algorithms 2019, 12(4), 85; https://doi.org/10.3390/a12040085 - 22 Apr 2019
Cited by 14 | Viewed by 4824
Abstract
During the last few decades, machine learning has constituted a significant tool in extracting useful knowledge from economic data for assisting decision-making. In this work, we evaluate the performance of weight-constrained recurrent neural networks in forecasting economic classification problems. These networks are efficiently [...] Read more.
During the last few decades, machine learning has constituted a significant tool in extracting useful knowledge from economic data for assisting decision-making. In this work, we evaluate the performance of weight-constrained recurrent neural networks in forecasting economic classification problems. These networks are efficiently trained with a recently-proposed training algorithm, which has two major advantages. Firstly, it exploits the numerical efficiency and very low memory requirements of the limited memory BFGS matrices; secondly, it utilizes a gradient-projection strategy for handling the bounds on the weights. The reported numerical experiments present the classification accuracy of the proposed model, providing empirical evidence that the application of the bounds on the weights of the recurrent neural network provides more stable and reliable learning. Full article
(This article belongs to the Special Issue Mining Humanistic Data 2019)
►▼ Show Figures

Figure 1

Figure 1
<p><math display="inline"><semantics> <msub> <mi>Log</mi> <mn>10</mn> </msub> </semantics></math>-scaled performance profiles for the bank management classification problem. The performance profile plots, for every <math display="inline"><semantics> <mrow> <mi>τ</mi> <mo>≥</mo> <mn>1</mn> </mrow> </semantics></math>, the proportion <math display="inline"><semantics> <mrow> <mi>P</mi> <mo>(</mo> <mi>τ</mi> <mo>)</mo> </mrow> </semantics></math> of simulations for which any training algorithm has a performance within a factor <math display="inline"><semantics> <mi>τ</mi> </semantics></math> of the best algorithm. (<b>a</b>) <math display="inline"><semantics> <msub> <mi>F</mi> <mn>1</mn> </msub> </semantics></math>-score. (<b>b</b>) Accuracy.</p> Full article ">Figure 2
<p><math display="inline"><semantics> <msub> <mi>Log</mi> <mn>10</mn> </msub> </semantics></math>-scaled performance profiles for the German credit approval classification problem. The performance profile plots, for every <math display="inline"><semantics> <mrow> <mi>τ</mi> <mo>≥</mo> <mn>1</mn> </mrow> </semantics></math>, the proportion <math display="inline"><semantics> <mrow> <mi>P</mi> <mo>(</mo> <mi>τ</mi> <mo>)</mo> </mrow> </semantics></math> of simulations for which any training algorithm has a performance within a factor <math display="inline"><semantics> <mi>τ</mi> </semantics></math> of the best algorithm. (<b>a</b>) <math display="inline"><semantics> <msub> <mi>F</mi> <mn>1</mn> </msub> </semantics></math>-score. (<b>b</b>) Accuracy.</p> Full article ">Figure 3
<p><math display="inline"><semantics> <msub> <mi>Log</mi> <mn>10</mn> </msub> </semantics></math>-scaled performance profiles for the banknote authentication classification problem. The performance profile plots, for every <math display="inline"><semantics> <mrow> <mi>τ</mi> <mo>≥</mo> <mn>1</mn> </mrow> </semantics></math>, the proportion <math display="inline"><semantics> <mrow> <mi>P</mi> <mo>(</mo> <mi>τ</mi> <mo>)</mo> </mrow> </semantics></math> of simulations for which any training algorithm has a performance within a factor <math display="inline"><semantics> <mi>τ</mi> </semantics></math> of the best algorithm. (<b>a</b>) <math display="inline"><semantics> <msub> <mi>F</mi> <mn>1</mn> </msub> </semantics></math>-score. (<b>b</b>) Accuracy.</p> Full article ">
15 pages, 3144 KiB  
Article
Horizontal Bending Angle Optimization Method for Scraper Conveyor Based on Improved Bat Algorithm
by Ting Liu, Chao Tan, Zhongbin Wang, Jing Xu, Yiqiao Man and Tuo Wang
Algorithms 2019, 12(4), 84; https://doi.org/10.3390/a12040084 - 22 Apr 2019
Cited by 11 | Viewed by 4802
Abstract
The horizontal bending angle of scraper conveyor has a great influence on the running resistance, the current consumption, coal winning efficiency of the working surface, etc. Approximately 1–3° is usually the range of horizontal bending angle, but does not indicate the optimum bending [...] Read more.
The horizontal bending angle of scraper conveyor has a great influence on the running resistance, the current consumption, coal winning efficiency of the working surface, etc. Approximately 1–3° is usually the range of horizontal bending angle, but does not indicate the optimum bending angle of the coal mining face. To find the optimal horizontal bending angle, an optimization method is proposed. A mathematical calculation model of the running resistance of the scraper is established based on the direction of the shearer operation. Then, a method of adjusting the step size of the search by inertia weight and expanding fly distance range obeying the t-distribution is proposed based on the basic bat algorithm (BA). Finally, an industrial application was conducted in 21220 Changcun fully mechanized coal mining face, Henan Province. The results show that the current consumption by the scraper conveyor was reduced by 31% when the horizontal bending angle of the S-bending area was 0.66°. Meanwhile, the theoretical current has good consistency with the experimental data, and the average absolute error was 3%. Full article
►▼ Show Figures

Figure 1

Figure 1
<p>Foraging process of the bat.</p> Full article ">Figure 2
<p>Distribution of inertia weight coefficient.</p> Full article ">Figure 3
<p>Probability density function curve of Cauchy distribution, t-distribution and Normal distribution.</p> Full article ">Figure 4
<p>The flowchart for optimizing horizontal bending angle of S-bending area based on MBA.</p> Full article ">Figure 5
<p>Comparison of optimization results of four different optimization algorithms.</p> Full article ">Figure 5 Cont.
<p>Comparison of optimization results of four different optimization algorithms.</p> Full article ">Figure 6
<p>Optimal horizontal bending angle and corresponding score distribution map.</p> Full article ">Figure 7
<p>Industrial application of the proposed method.</p> Full article ">Figure 8
<p>Comparison between the measured and theoretical current of scraper conveyor when <span class="html-italic">m</span> = 1.</p> Full article ">Figure 8 Cont.
<p>Comparison between the measured and theoretical current of scraper conveyor when <span class="html-italic">m</span> = 1.</p> Full article ">Figure 9
<p>Comparison between the measured and theoretical current of scraper conveyor when <span class="html-italic">m</span> = 2.</p> Full article ">
10 pages, 1885 KiB  
Article
The Optimization Algorithm of the Forced Current Cathodic Protection Base on Simulated Annealing
by Chunfeng Song, Mei Wang, Xuebin Qin, Pai Wang and Bao Liu
Algorithms 2019, 12(4), 83; https://doi.org/10.3390/a12040083 - 21 Apr 2019
Cited by 4 | Viewed by 4008
Abstract
The grounding grid of a substation is important for the safety of substation equipment. Especially to address the difficulty of parameter design in the auxiliary anode system of a grounding grid, an algorithm is proposed that is an optimization algorithm for the auxiliary [...] Read more.
The grounding grid of a substation is important for the safety of substation equipment. Especially to address the difficulty of parameter design in the auxiliary anode system of a grounding grid, an algorithm is proposed that is an optimization algorithm for the auxiliary anode system of a grounding grid based on improved simulated annealing. The mathematical model of the auxiliary anode system is inferred from the mathematical model of cathodic protection. On that basis, the parameters of the finite element model are optimized with the improved simulated annealing algorithm, thereby the auxiliary anode system of a grounding grid with optimized parameters is structured. Then the algorithm is proven as valid through experiments. The precision of the optimized parameters is improved by about 1.55% with respect to the Variable Metric Method and the Genetic Algorithm, so it can provide a basis for parameter design in the auxiliary anode system of a grounding grid. Full article
(This article belongs to the Special Issue Selected Papers from 2018 International Symposium on Computer, Consumer and Control)
►▼ Show Figures

Figure 1

Figure 1
<p>Grounding grid cathodic protection model.</p> Full article ">Figure 2
<p>Flow chart of optimization algorithm for auxiliary anode system based on simulated annealing.</p> Full article ">Figure 3
<p>Finite element splitting diagram of the grounding grid surface.</p> Full article ">Figure 4
<p>Surface potential distribution map of grounding grid based on simulated annealing optimization.</p> Full article ">Figure 5
<p>Ground potential distribution caused by different positions when the anode potential is 90 V.</p> Full article ">
22 pages, 10930 KiB  
Article
Image Error Concealment Based on Deep Neural Network
by Zhiqiang Zhang, Rong Huang, Fang Han and Zhijie Wang
Algorithms 2019, 12(4), 82; https://doi.org/10.3390/a12040082 - 19 Apr 2019
Cited by 4 | Viewed by 5620
Abstract
In this paper, we propose a novel spatial image error concealment (EC) method based on deep neural network. Considering that the natural images have local correlation and non-local self-similarity, we use the local information to predict the missing pixels and the non-local information [...] Read more.
In this paper, we propose a novel spatial image error concealment (EC) method based on deep neural network. Considering that the natural images have local correlation and non-local self-similarity, we use the local information to predict the missing pixels and the non-local information to correct the predictions. The deep neural network we utilize can be divided into two parts: the prediction part and the auto-encoder (AE) part. The first part utilizes the local correlation among pixels to predict the missing ones. The second part extracts image features, which are used to collect similar samples from the whole image. In addition, a novel adaptive scan order based on the joint credibility of the support area and reconstruction is also proposed to alleviate the error propagation problem. The experimental results show that the proposed method can reconstruct corrupted images effectively and outperform the compared state-of-the-art methods in terms of objective and perceptual metrics. Full article
►▼ Show Figures

Figure 1

Figure 1
<p>Structure of the corrupted image. Each square stands for one pixel. The black pixels are unavailable ones. The white pixels are correctly received ones. The pixel being predicted is marked in red, and the pixels marked blue are the pixels corresponding to the current pixel <math display="inline"><semantics> <mrow> <msubsup> <mi mathvariant="bold">y</mi> <mi>i</mi> <mi mathvariant="normal">u</mi> </msubsup> </mrow> </semantics></math> of the similar samples.</p> Full article ">Figure 2
<p>Block diagram of the proposed method. The missing pixel <math display="inline"><semantics> <mrow> <msubsup> <mi mathvariant="bold">y</mi> <mi>i</mi> <mi mathvariant="normal">u</mi> </msubsup> </mrow> </semantics></math> is under process. The square patches <math display="inline"><semantics> <mrow> <msub> <mi mathvariant="normal">t</mi> <mi>i</mi> </msub> <mo stretchy="false">(</mo> <mi>i</mi> <mo>=</mo> <mn>1</mn> <mo>,</mo> <mn>2</mn> <mo>,</mo> <mo>…</mo> <mo>,</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> </semantics></math> are the collected samples for training. The square patches <math display="inline"><semantics> <mrow> <msub> <mi mathvariant="bold">s</mi> <mi>i</mi> </msub> <mo stretchy="false">(</mo> <mi>i</mi> <mo>=</mo> <mn>1</mn> <mo>,</mo> <mn>2</mn> <mo>,</mo> <mo>…</mo> <mo>,</mo> <mi>m</mi> <mo stretchy="false">)</mo> </mrow> </semantics></math> are the samples that are similar to the current support area <math display="inline"><semantics> <mrow> <msubsup> <mi mathvariant="bold">y</mi> <mi>i</mi> <mi mathvariant="normal">s</mi> </msubsup> </mrow> </semantics></math>.</p> Full article ">Figure 3
<p>Structure of the utilized neural networks. (<b>a</b>) The structure of auto-encoder part network. (<b>b</b>) The structure of the prediction part network.</p> Full article ">Figure 4
<p>Structure of the designed auto-encoder prediction (AE-P) network.</p> Full article ">Figure 5
<p>The red square is the current missing pixel, the gray squares are the available pixels, and the black squares are the unavailable pixels. (<b>a</b>) The template with square shape. (<b>b</b>) The context of the current missing pixel through matching the square template.</p> Full article ">Figure 6
<p>The eight different templates used in our method. The black squares stand for the missing pixels, and the white squares are the successfully received ones.</p> Full article ">Figure 7
<p>The red square stands for the current missing pixel. Four support area can be found for the currently missing pixel.</p> Full article ">Figure 8
<p>The procedure of transforming the shape from <span class="html-italic">up-left</span> into the standard shape <span class="html-italic">down-left</span>.</p> Full article ">Figure 9
<p>Structure of the augmented samples for selecting in pixel space. Each square stands for one pixel. The green part are the added pixels.</p> Full article ">Figure 10
<p>The initialization confidence of pixels in the received image. Each square stands for one pixel. The gray pixels with label 1 represent the correctly received pixels, while the green ones with label 0 are the missing pixels. The red pixels are the currently being filled. The part in the red box is the support areas of the missing pixel <math display="inline"><semantics> <mrow> <msub> <mi mathvariant="bold">y</mi> <mn>1</mn> </msub> </mrow> </semantics></math>.</p> Full article ">Figure 11
<p>Typical block loss mode. (<b>a</b>) Isolate block loss. (<b>b</b>) Consecutive block loss. (<b>c</b>) Random block loss.</p> Full article ">Figure 12
<p>The 13 test images used in our experiments. From left to right and top to bottom: Baboon, Barbara, Boat, Butterfly, Columbia, Cornfield, Couple, Goldhill, Hat, Man, Peppers, Tower.</p> Full article ">Figure 13
<p>The influence of the proposed correction and adaptive scan order to the final error concealment (EC) performance under the <math display="inline"><semantics> <mrow> <mn>16</mn> <mo>×</mo> <mn>16</mn> </mrow> </semantics></math> regular isolated loss mode.</p> Full article ">Figure 14
<p>The influence of the proposed correction and adaptive scan order to the final EC performance under the <math display="inline"><semantics> <mrow> <mn>16</mn> <mo>×</mo> <mn>16</mn> </mrow> </semantics></math> regular consecutive loss mode.</p> Full article ">Figure 15
<p>The influence of the proposed correction and adaptive scan order to the final EC performance under the <math display="inline"><semantics> <mrow> <mn>16</mn> <mo>×</mo> <mn>16</mn> </mrow> </semantics></math> random loss mode.</p> Full article ">Figure 16
<p>Subjective quality comparison of the proposed correction and adaptive scan order on the Cameraman image with <math display="inline"><semantics> <mrow> <mn>16</mn> <mo>×</mo> <mn>16</mn> </mrow> </semantics></math> regular isolated loss. The reconstructed details are shown in the lower right corner of each image. (<b>a</b>) The received image. (<b>b</b>) The original image. (<b>c</b>) The reconstructed image with scenario ‘Cor(off)-Ord(on)’. (<b>d</b>) The reconstructed image with scenario ‘Cor(on)-Ord(off)’. (<b>e</b>) The reconstructed image with scenario ‘Cor(on)-Ord(on)’.</p> Full article ">Figure 17
<p>Subjective quality comparison of the proposed correction and adaptive scan order on the Peppers image with <math display="inline"><semantics> <mrow> <mn>16</mn> <mo>×</mo> <mn>16</mn> </mrow> </semantics></math> regular consecutive loss. The reconstructed details are shown in the lower right corner of each image. (<b>a</b>) The received image. (<b>b</b>) The original image. (<b>c</b>) The reconstructed image with scenario ‘Cor(off)-Ord(on)’. (<b>d</b>) The reconstructed image with scenario ‘Cor(on)-Ord(off)’. (<b>e</b>) The reconstructed image with scenario ‘Cor(on)-Ord(on)’.</p> Full article ">Figure 18
<p>Subjective quality comparison of the proposed correction and adaptive scan order on the Butterfly image with <math display="inline"><semantics> <mrow> <mn>16</mn> <mo>×</mo> <mn>16</mn> </mrow> </semantics></math> random loss. The reconstructed details are shown in the lower right corner of each image. (<b>a</b>) The received image. (<b>b</b>) The original image. (<b>c</b>) The reconstructed image with scenario ‘Cor(off)-Ord(on)’. (<b>d</b>) The reconstructed image with scenario ‘Cor(on)-Ord(off)’. (<b>e</b>) The reconstructed image with scenario ‘Cor(on)-Ord(on)’.</p> Full article ">Figure 19
<p>Subjective comparison of different EC algorithms on the Barbara image with <math display="inline"><semantics> <mrow> <mn>16</mn> <mo>×</mo> <mn>16</mn> </mrow> </semantics></math> isolate block loss. The corresponding PSNR and SSIM values are also shown in the upper left corner.</p> Full article ">Figure 20
<p>Subjective comparison of different EC algorithms on the Butterfly image with <math display="inline"><semantics> <mrow> <mn>16</mn> <mo>×</mo> <mn>16</mn> </mrow> </semantics></math> consecutive block loss. The corresponding PSNR and SSIM values are also shown in the upper left corner.</p> Full article ">Figure 21
<p>Subjective comparison of different EC algorithms on the Cameraman image with <math display="inline"><semantics> <mrow> <mn>16</mn> <mo>×</mo> <mn>16</mn> </mrow> </semantics></math> random block loss. The corresponding PSNR and SSIM values are also shown in the upper left corner.</p> Full article ">
24 pages, 581 KiB  
Article
Direct Superbubble Detection
by Fabian Gärtner and Peter F. Stadler
Algorithms 2019, 12(4), 81; https://doi.org/10.3390/a12040081 - 17 Apr 2019
Cited by 2 | Viewed by 4923
Abstract
Superbubbles are a class of induced subgraphs in digraphs that play an essential role in assembly algorithms for high-throughput sequencing data. They are connected with the remainder of the host digraph by a single entrance and a single exit vertex. Linear-time algorithms for [...] Read more.
Superbubbles are a class of induced subgraphs in digraphs that play an essential role in assembly algorithms for high-throughput sequencing data. They are connected with the remainder of the host digraph by a single entrance and a single exit vertex. Linear-time algorithms for the enumeration superbubbles recently have become available. Current approaches require the decomposition of the input digraph into strongly-connected components, which are then analyzed separately. In principle, a single depth-first search could be used, provided one can guarantee that the root of the depth-first search (DFS)-tree is not itself located in the interior or the exit point of a superbubble. Here, we describe a linear-time algorithm to determine suitable roots for a DFS-forest that is guaranteed to identify the superbubbles in a digraph correctly. In addition to the advantages of a more straightforward implementation, we observe a nearly three-fold gain in performance on real-world datasets. We present a reference implementation of the new algorithm that accepts many commonly-used input formats for digraphs. It is available as open source from github. Full article
►▼ Show Figures

Figure 1

Figure 1
<p>Illustration of the algorithm <tt>Superbubble</tt> on a digraph <span class="html-italic">G</span> with cycles. The top panel shows the input digraph. The DFS-tree <span class="html-italic">T</span> is rooted at one and covers <math display="inline"><semantics> <mrow> <mi>V</mi> <mo>[</mo> <mi>r</mi> <mo>]</mo> <mo>=</mo> <mi>V</mi> <mo>(</mo> <mi>G</mi> <mo>)</mo> <mo>\</mo> <mo>{</mo> <mn>15</mn> <mo>}</mo> </mrow> </semantics></math>. The table below gives the values of <math display="inline"><semantics> <mi mathvariant="bold">OutParent</mi> </semantics></math> and <math display="inline"><semantics> <mi mathvariant="bold">OutChild</mi> </semantics></math> as a function of the reverse postorder <math display="inline"><semantics> <mover accent="true"> <mi>π</mi> <mo stretchy="false">¯</mo> </mover> </semantics></math> of <span class="html-italic">T</span>. In the final line, matching pairs of parentheses indicate entrances and exits of the weak superbubbles in <math display="inline"><semantics> <mrow> <mi>V</mi> <mo>[</mo> <mi>r</mi> <mo>]</mo> </mrow> </semantics></math>. This corresponds to the intervals that fulfill (F1) and (F2).</p> Full article ">Figure 2
<p>Relationships of distinct <span class="html-italic">C</span>-intervals. The four possibilities for the relative location of two distinct <span class="html-italic">C</span>-intervals are shown on a linear layout of a cycle <span class="html-italic">C</span> with five vertices (<math display="inline"><semantics> <mrow> <mn>0</mn> <mo>,</mo> <mn>1</mn> <mo>,</mo> <mn>2</mn> <mo>,</mo> <mn>3</mn> <mo>,</mo> <mn>4</mn> </mrow> </semantics></math>). Left top: the <span class="html-italic">C</span>-intervals <math display="inline"><semantics> <mrow> <mn>0</mn> <mo>,</mo> <mn>2</mn> </mrow> </semantics></math> and <math display="inline"><semantics> <mrow> <mn>2</mn> <mo>,</mo> <mn>4</mn> </mrow> </semantics></math> are <span class="html-italic">disjoint</span>. Right top: <math display="inline"><semantics> <mrow> <mn>0</mn> <mo>,</mo> <mn>4</mn> </mrow> </semantics></math> <span class="html-italic">includes</span> <math display="inline"><semantics> <mrow> <mn>1</mn> <mo>,</mo> <mn>3</mn> </mrow> </semantics></math>. Left bottom: <math display="inline"><semantics> <mrow> <mn>1</mn> <mo>,</mo> <mn>3</mn> </mrow> </semantics></math> <span class="html-italic">extends</span> <math display="inline"><semantics> <mrow> <mn>0</mn> <mo>,</mo> <mn>2</mn> </mrow> </semantics></math>, but not <span class="html-italic">vice versa</span>. Right bottom: <math display="inline"><semantics> <mrow> <mn>0</mn> <mo>,</mo> <mn>4</mn> </mrow> </semantics></math> and <math display="inline"><semantics> <mrow> <mn>3</mn> <mo>,</mo> <mn>1</mn> </mrow> </semantics></math> <span class="html-italic">extend each other</span>. Together, the two <span class="html-italic">C</span>-intervals cover <span class="html-italic">C</span>.</p> Full article ">Figure 3
<p><math display="inline"><semantics> <mrow> <mover> <mo>⇝</mo> <mstyle scriptlevel="1" displaystyle="false"> <mi>C</mi> </mstyle> </mover> </mrow> </semantics></math>-covers. (<b>a</b>) The green cycle <span class="html-italic">C</span> in the top panel has five <math display="inline"><semantics> <mrow> <mover> <mo>⇝</mo> <mstyle scriptlevel="1" displaystyle="false"> <mi>C</mi> </mstyle> </mover> </mrow> </semantics></math>-paths indicated in red. In the middle panel, <span class="html-italic">C</span> is laid out linearly to emphasize the <math display="inline"><semantics> <mrow> <mover> <mo>⇝</mo> <mstyle scriptlevel="1" displaystyle="false"> <mi>C</mi> </mstyle> </mover> </mrow> </semantics></math>-covered intervals. Below, the clean <math display="inline"><semantics> <mrow> <mover> <mo>⇝</mo> <mstyle scriptlevel="1" displaystyle="false"> <mi>C</mi> </mstyle> </mover> </mrow> </semantics></math>-cover obtained by removing all <math display="inline"><semantics> <mrow> <mover> <mo>⇝</mo> <mstyle scriptlevel="1" displaystyle="false"> <mi>C</mi> </mstyle> </mover> </mrow> </semantics></math>-intervals that are contained in longer ones. Note that every <math display="inline"><semantics> <mrow> <mover> <mo>⇝</mo> <mstyle scriptlevel="1" displaystyle="false"> <mi>C</mi> </mstyle> </mover> </mrow> </semantics></math>-interval is extended by another one; hence, the <math display="inline"><semantics> <mrow> <mover> <mo>⇝</mo> <mstyle scriptlevel="1" displaystyle="false"> <mi>C</mi> </mstyle> </mover> </mrow> </semantics></math>-cover is total. (<b>b</b>) Again, the top panel highlights <span class="html-italic">C</span> in green and the <math display="inline"><semantics> <mrow> <mover> <mo>⇝</mo> <mstyle scriptlevel="1" displaystyle="false"> <mi>C</mi> </mstyle> </mover> </mrow> </semantics></math>-paths in red. The linear layout below highlights that Vertex 1 is not <math display="inline"><semantics> <mrow> <mover> <mo>⇝</mo> <mstyle scriptlevel="1" displaystyle="false"> <mi>C</mi> </mstyle> </mover> </mrow> </semantics></math>-covered. Thus, it is a <math display="inline"><semantics> <mrow> <mover> <mo>⇝</mo> <mstyle scriptlevel="1" displaystyle="false"> <mi>C</mi> </mstyle> </mover> </mrow> </semantics></math>-cut vertex.</p> Full article ">Figure 3 Cont.
<p><math display="inline"><semantics> <mrow> <mover> <mo>⇝</mo> <mstyle scriptlevel="1" displaystyle="false"> <mi>C</mi> </mstyle> </mover> </mrow> </semantics></math>-covers. (<b>a</b>) The green cycle <span class="html-italic">C</span> in the top panel has five <math display="inline"><semantics> <mrow> <mover> <mo>⇝</mo> <mstyle scriptlevel="1" displaystyle="false"> <mi>C</mi> </mstyle> </mover> </mrow> </semantics></math>-paths indicated in red. In the middle panel, <span class="html-italic">C</span> is laid out linearly to emphasize the <math display="inline"><semantics> <mrow> <mover> <mo>⇝</mo> <mstyle scriptlevel="1" displaystyle="false"> <mi>C</mi> </mstyle> </mover> </mrow> </semantics></math>-covered intervals. Below, the clean <math display="inline"><semantics> <mrow> <mover> <mo>⇝</mo> <mstyle scriptlevel="1" displaystyle="false"> <mi>C</mi> </mstyle> </mover> </mrow> </semantics></math>-cover obtained by removing all <math display="inline"><semantics> <mrow> <mover> <mo>⇝</mo> <mstyle scriptlevel="1" displaystyle="false"> <mi>C</mi> </mstyle> </mover> </mrow> </semantics></math>-intervals that are contained in longer ones. Note that every <math display="inline"><semantics> <mrow> <mover> <mo>⇝</mo> <mstyle scriptlevel="1" displaystyle="false"> <mi>C</mi> </mstyle> </mover> </mrow> </semantics></math>-interval is extended by another one; hence, the <math display="inline"><semantics> <mrow> <mover> <mo>⇝</mo> <mstyle scriptlevel="1" displaystyle="false"> <mi>C</mi> </mstyle> </mover> </mrow> </semantics></math>-cover is total. (<b>b</b>) Again, the top panel highlights <span class="html-italic">C</span> in green and the <math display="inline"><semantics> <mrow> <mover> <mo>⇝</mo> <mstyle scriptlevel="1" displaystyle="false"> <mi>C</mi> </mstyle> </mover> </mrow> </semantics></math>-paths in red. The linear layout below highlights that Vertex 1 is not <math display="inline"><semantics> <mrow> <mover> <mo>⇝</mo> <mstyle scriptlevel="1" displaystyle="false"> <mi>C</mi> </mstyle> </mover> </mrow> </semantics></math>-covered. Thus, it is a <math display="inline"><semantics> <mrow> <mover> <mo>⇝</mo> <mstyle scriptlevel="1" displaystyle="false"> <mi>C</mi> </mstyle> </mover> </mrow> </semantics></math>-cut vertex.</p> Full article ">Figure 4
<p>One-vertex cover. As in <a href="#algorithms-12-00081-f003" class="html-fig">Figure 3</a>, the cycle <span class="html-italic">C</span> and the <math display="inline"><semantics> <mrow> <mover> <mo>⇝</mo> <mstyle scriptlevel="1" displaystyle="false"> <mi>C</mi> </mstyle> </mover> </mrow> </semantics></math>-paths are highlighted in green and red, respectively. The paths <math display="inline"><semantics> <mrow> <mo>(</mo> <mn>0</mn> <mo>,</mo> <mn>5</mn> <mo>,</mo> <mn>4</mn> <mo>)</mo> </mrow> </semantics></math> and <math display="inline"><semantics> <mrow> <mo>(</mo> <mn>3</mn> <mo>,</mo> <mn>5</mn> <mo>,</mo> <mn>1</mn> <mo>)</mo> </mrow> </semantics></math> imply that <math display="inline"><semantics> <mrow> <mn>0</mn> <mo>,</mo> <mn>4</mn> </mrow> </semantics></math> and <math display="inline"><semantics> <mrow> <mn>3</mn> <mo>,</mo> <mn>1</mn> </mrow> </semantics></math> are <math display="inline"><semantics> <mrow> <mover> <mo>⇝</mo> <mstyle scriptlevel="1" displaystyle="false"> <mi>C</mi> </mstyle> </mover> </mrow> </semantics></math>-covered. It is a one-vertex cover conforming to Lemma 9.</p> Full article ">Figure 5
<p>A digraph <span class="html-italic">G</span> without any legitimate root. In <span class="html-italic">G</span> are 16 isomorphic cycles containing eight of the 12 vertices, all of which contain <math display="inline"><semantics> <mrow> <mo>{</mo> <mn>1</mn> <mo>,</mo> <mn>3</mn> <mo>,</mo> <mn>5</mn> <mo>,</mo> <mn>7</mn> <mo>}</mo> </mrow> </semantics></math>. The superbubbles <math display="inline"><semantics> <mrow> <mo>〈</mo> <mn>1</mn> <mo>,</mo> <mn>3</mn> <mo>〉</mo> </mrow> </semantics></math>, <math display="inline"><semantics> <mrow> <mo>〈</mo> <mn>3</mn> <mo>,</mo> <mn>5</mn> <mo>〉</mo> </mrow> </semantics></math>, <math display="inline"><semantics> <mrow> <mo>〈</mo> <mn>5</mn> <mo>,</mo> <mn>7</mn> <mo>〉</mo> </mrow> </semantics></math>, and <math display="inline"><semantics> <mrow> <mo>〈</mo> <mn>7</mn> <mo>,</mo> <mn>1</mn> <mo>〉</mo> </mrow> </semantics></math> cover <span class="html-italic">G</span> entirely, i.e., every entrance of a superbubble is also the exit of another one, and all other vertices are interior vertices of a superbubble.</p> Full article ">
29 pages, 7077 KiB  
Article
An Improved Squirrel Search Algorithm for Global Function Optimization
by Yanjiao Wang and Tianlin Du
Algorithms 2019, 12(4), 80; https://doi.org/10.3390/a12040080 - 17 Apr 2019
Cited by 35 | Viewed by 7148
Abstract
An improved squirrel search algorithm (ISSA) is proposed in this paper. The proposed algorithm contains two searching methods, one is the jumping search method, and the other is the progressive search method. The practical method used in the evolutionary process is selected automatically [...] Read more.
An improved squirrel search algorithm (ISSA) is proposed in this paper. The proposed algorithm contains two searching methods, one is the jumping search method, and the other is the progressive search method. The practical method used in the evolutionary process is selected automatically through the linear regression selection strategy, which enhances the robustness of squirrel search algorithm (SSA). For the jumping search method, the ‘escape’ operation develops the search space sufficiently and the ‘death’ operation further explores the developed space, which balances the development and exploration ability of SSA. Concerning the progressive search method, the mutation operation fully preserves the current evolutionary information and pays more attention to maintain the population diversity. Twenty-one benchmark functions are selected to test the performance of ISSA. The experimental results show that the proposed algorithm can improve the convergence accuracy, accelerate the convergence speed as well as maintain the population diversity. The statistical test proves that ISSA has significant advantages compared with SSA. Furthermore, compared with five other intelligence evolutionary algorithms, the experimental results and statistical tests also show that ISSA has obvious advantages on convergence accuracy, convergence speed and robustness. Full article
►▼ Show Figures

Figure 1

Figure 1
<p>The procedure of the standard squirrel search algorithm (SSA).</p> Full article ">Figure 2
<p>The illustration of the linear regression selection strategy.</p> Full article ">Figure 3
<p>The procedure of improved squirrel search algorithm (ISSA).</p> Full article ">Figure 4
<p>Convergence curves of the proposed methods and SSA.</p> Full article ">Figure 5
<p>The convergence curves of ISSA and other algorithms.</p> Full article ">Figure 5 Cont.
<p>The convergence curves of ISSA and other algorithms.</p> Full article ">
17 pages, 966 KiB  
Article
Speech Act Theory as an Evaluation Tool for Human–Agent Communication
by Nader Hanna and Deborah Richards
Algorithms 2019, 12(4), 79; https://doi.org/10.3390/a12040079 - 17 Apr 2019
Cited by 8 | Viewed by 11644
Abstract
Effective communication in task-oriented situations requires high-level interactions. For human–agent collaboration, tasks need to be coordinated in a way that ensures mutual understanding. Speech Act Theory (SAT) aims to understand how utterances can be used to achieve actions. SAT consists of three components: [...] Read more.
Effective communication in task-oriented situations requires high-level interactions. For human–agent collaboration, tasks need to be coordinated in a way that ensures mutual understanding. Speech Act Theory (SAT) aims to understand how utterances can be used to achieve actions. SAT consists of three components: locutionary act, illocutionary act, and perlocutionary act. This paper evaluates the agent’s verbal communication while collaborating with humans. SAT was used to anatomize the structure of the agent’s speech acts (locutionary acts), the agent’s intention behind the speech acts (illocutionary acts), and the effects on the human’s mental state (perlocutionary acts). Moreover, this paper studies the impact of human perceptions of the agent’s speech acts on the perception of collaborative performance with the agent. Full article
(This article belongs to the Special Issue Social Computing and Multiagent Systems)
►▼ Show Figures

Figure 1

Figure 1
<p>Screenshot from the scenario in Omosa Virtual World.</p> Full article ">Figure 2
<p>Participants’ evaluation of the agent’s locutionary acts.</p> Full article ">Figure 3
<p>Evaluating the agent’s illocutionary acts.</p> Full article ">Figure 4
<p>Evaluating the agent’s perlocutionary acts.</p> Full article ">
15 pages, 344 KiB  
Article
Applications of Non-Uniquely Decodable Codes to Privacy-Preserving High-Entropy Data Representation
by Muhammed Oğuzhan Külekci and Yasin Öztürk
Algorithms 2019, 12(4), 78; https://doi.org/10.3390/a12040078 - 17 Apr 2019
Cited by 1 | Viewed by 4345
Abstract
Non-uniquely-decodable (non-UD) codes can be defined as the codes that cannot be uniquely decoded without additional disambiguation information. These are mainly the class of non–prefix–free codes, where a code-word can be a prefix of other(s), and thus, the code-word boundary information is essential [...] Read more.
Non-uniquely-decodable (non-UD) codes can be defined as the codes that cannot be uniquely decoded without additional disambiguation information. These are mainly the class of non–prefix–free codes, where a code-word can be a prefix of other(s), and thus, the code-word boundary information is essential for correct decoding. Due to their inherent unique decodability problem, such non-UD codes have not received much attention except a few studies, in which using compressed data structures to represent the disambiguation information efficiently had been previously proposed. It had been shown before that the compression ratio can get quite close to Huffman/Arithmetic codes with an additional capability of providing direct access in compressed data, which is a missing feature in the regular Huffman codes. In this study we investigate non-UD codes in another dimension addressing the privacy of the high-entropy data. We particularly focus on such massive volumes, where typical examples are encoded video or similar multimedia files. Representation of such a volume with non–UD coding creates two elements as the disambiguation information and the payload, where decoding the original data from these elements becomes hard when one of them is missing. We make use of this observation for privacy concerns. and study the space consumption as well as the hardness of that decoding. We conclude that non-uniquely-decodable codes can be an alternative to selective encryption schemes that aim to secure only part of the data when data is huge. We provide a freely available software implementation of the proposed scheme as well. Full article
(This article belongs to the Special Issue String Matching and Its Applications)
►▼ Show Figures

Figure 1

Figure 1
<p>A simple sketch of the non-prefix-free coding of an input bit sequence <math display="inline"><semantics> <mi mathvariant="script">A</mi> </semantics></math>, where <math display="inline"><semantics> <mi mathvariant="script">B</mi> </semantics></math> is the representation of <math display="inline"><semantics> <mi mathvariant="script">A</mi> </semantics></math> with the block length <math display="inline"><semantics> <mrow> <mi>d</mi> <mo>=</mo> <mn>3</mn> </mrow> </semantics></math>. <math display="inline"><semantics> <msup> <mo>Σ</mo> <mo>′</mo> </msup> </semantics></math> is a random permutation of the corresponding alphabet <math display="inline"><semantics> <mo>Σ</mo> </semantics></math>, and <span class="html-italic">W</span> is the non-prefix-free code-word set generated for <math display="inline"><semantics> <msup> <mo>Σ</mo> <mo>′</mo> </msup> </semantics></math> according to Definition 2. The disambiguation information <math display="inline"><semantics> <mrow> <mi>D</mi> <mi>i</mi> <mi>s</mi> <mi>I</mi> <mi>n</mi> <mi>f</mi> <mi>o</mi> <mo>(</mo> <mi mathvariant="script">A</mi> <mo>)</mo> </mrow> </semantics></math> is computed according to Lemma 2.</p> Full article ">Figure 2
<p>The representation of the code-word lengths to specify the code-word boundaries on the NPF stream.</p> Full article ">Figure 3
<p>NPF encoding/decoding speed in megabytes per second on different file sizes with different <span class="html-italic">d</span> values. Note that “NoMap” means no look-up table is used.</p> Full article ">
24 pages, 2210 KiB  
Article
Embedding Equality Constraints of Optimization Problems into a Quantum Annealer
by Tomas Vyskocil and Hristo Djidjev
Algorithms 2019, 12(4), 77; https://doi.org/10.3390/a12040077 - 17 Apr 2019
Cited by 16 | Viewed by 5682
Abstract
Quantum annealers such as D-Wave machines are designed to propose solutions for quadratic unconstrained binary optimization (QUBO) problems by mapping them onto the quantum processing unit, which tries to find a solution by measuring the parameters of a minimum-energy state of the quantum [...] Read more.
Quantum annealers such as D-Wave machines are designed to propose solutions for quadratic unconstrained binary optimization (QUBO) problems by mapping them onto the quantum processing unit, which tries to find a solution by measuring the parameters of a minimum-energy state of the quantum system. While many NP-hard problems can be easily formulated as binary quadratic optimization problems, such formulations almost always contain one or more constraints, which are not allowed in a QUBO. Embedding such constraints as quadratic penalties is the standard approach for addressing this issue, but it has drawbacks such as the introduction of large coefficients and using too many additional qubits. In this paper, we propose an alternative approach for implementing constraints based on a combinatorial design and solving mixed-integer linear programming (MILP) problems in order to find better embeddings of constraints of the type ∑ x i = k for binary variables x i. Our approach is scalable to any number of variables and uses a linear number of ancillary variables for a fixed k. Full article
(This article belongs to the Special Issue Quantum Optimization Theory, Algorithms, and Applications)
►▼ Show Figures

Figure 1

Figure 1
<p>The Chimera interconnection graph for the D-Wave 2X system is a <math display="inline"><semantics> <mrow> <mn>12</mn> <mo>×</mo> <mn>12</mn> </mrow> </semantics></math> array of <span class="html-italic">unit cells</span>, where each cell is a <math display="inline"><semantics> <mrow> <mn>4</mn> <mo>×</mo> <mn>4</mn> </mrow> </semantics></math> bipartite graph.</p> Full article ">Figure 2
<p>Illustration of the internal (<span class="html-fig-inline" id="algorithms-12-00077-i001"> <img alt="Algorithms 12 00077 i001" src="/algorithms/algorithms-12-00077/article_deploy/html/images/algorithms-12-00077-i001.png"/></span>) and problem (<span class="html-fig-inline" id="algorithms-12-00077-i002"> <img alt="Algorithms 12 00077 i002" src="/algorithms/algorithms-12-00077/article_deploy/html/images/algorithms-12-00077-i002.png"/></span>) type gadgets and tiles. (<b>a</b>) A cell of the Chimera graph. Short lines denote couplers connecting the cell to other cells. (<b>b</b>) The logical structure of the corresponding internal gadget, showing the types of the variables, and, as an example, a concrete assignment of values to the interface variables. (<b>c</b>) The corresponding tile as used in our embedding illustrations, with red color for +1 and green for −1 type variables. Analogous illustrations for the problem type gadget and tile are found in (<b>d</b>–<b>f</b>).</p> Full article ">Figure 3
<p>The set of the good tiles.</p> Full article ">Figure 4
<p>Ising proram construction for the case <math display="inline"><semantics> <mrow> <mi>n</mi> <mo>=</mo> <mn>6</mn> </mrow> </semantics></math>, <math display="inline"><semantics> <mrow> <mi>k</mi> <mo>=</mo> <mn>3</mn> </mrow> </semantics></math>.</p> Full article ">Figure 5
<p>Optimal tiling of <math display="inline"><semantics> <mrow> <mi mathvariant="italic">Is</mi> <mo stretchy="false">(</mo> <mi>R</mi> <mo stretchy="false">)</mo> </mrow> </semantics></math>.</p> Full article ">Figure 6
<p>A row <math display="inline"><semantics> <msub> <mi>R</mi> <mi>i</mi> </msub> </semantics></math> of <span class="html-italic">R</span>, denoted by <math display="inline"><semantics> <msub> <mi>R</mi> <mi>i</mi> </msub> </semantics></math>, with an assignment of values to the program variables/tiles.</p> Full article ">Figure 7
<p>Illustration of the internal type gadgets and tile for the case <math display="inline"><semantics> <mrow> <mi>k</mi> <mo>=</mo> <mn>1</mn> </mrow> </semantics></math>. (<b>a</b>) A cell of the Chimera graph. Short lines indicate the couplers connecting to the neighboring cells (some may be missing for boundary cells). (<b>b</b>) The logical structure of the the corresponding internal gadget. There are two edges (couplers) shown in red (thicker line in b&amp;w) in (<b>a</b>) with weights (in he example) <math display="inline"><semantics> <mrow> <mo>−</mo> <mn>1</mn> </mrow> </semantics></math> and 1 connecting it to the neighboring cells in the row. The coupler shown in blue, in combination with the red coupler on top, is used in the gadget discussed in <a href="#sec7dot2-algorithms-12-00077" class="html-sec">Section 7.2</a>. (<b>c</b>) The corresponding tile as used in our embedding illustrations, with red color for +1 and green for −1 type variables.</p> Full article ">Figure 8
<p>The set of the good tiles for the case <math display="inline"><semantics> <mrow> <mi>k</mi> <mo>=</mo> <mn>1</mn> </mrow> </semantics></math>.</p> Full article ">Figure 9
<p>(<b>a</b>) Ising program <math display="inline"><semantics> <mrow> <mi mathvariant="script">I</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> </semantics></math> for the case <math display="inline"><semantics> <mrow> <mi>n</mi> <mo>=</mo> <mn>5</mn> </mrow> </semantics></math>, <math display="inline"><semantics> <mrow> <mi>k</mi> <mo>=</mo> <mn>1</mn> </mrow> </semantics></math>. (<b>b</b>) The structure of an optimal tiling of <math display="inline"><semantics> <mrow> <mi mathvariant="script">I</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> </semantics></math>. In such tiling, adjacent halves of neighboring tiles should be in different colors.</p> Full article ">Figure 10
<p>This example illustrates the connections between the tiles in a solution for the multi-row case for a Chimera graph of size <math display="inline"><semantics> <mrow> <mn>4</mn> <mo>×</mo> <mn>4</mn> </mrow> </semantics></math> cells, each cell representing a tile with one problem variable, with the exception of first and last tiles that contain no problem variables.</p> Full article ">Figure 11
<p>Positions of the <span class="html-italic">x</span> and <span class="html-italic">t</span> variables in a Chimera graph cell for the optimization problem (<b>a</b>) in the single-row embedding, and (<b>b</b>) for the extra gadgets in the multi-row embedding.</p> Full article ">Figure 12
<p>The structure of the tiles for the case of <math display="inline"><semantics> <mrow> <mi mathvariant="italic">gap</mi> <mo>=</mo> <mn>4</mn> </mrow> </semantics></math>. (<b>a</b>) A cell of the Chimera graph. Short lines indicate the couplers connecting to the neighboring cells. (<b>b</b>) The logical structure of the tile corresponding to that cell. Edges correspond to couplers shown in red in (<b>a</b>).</p> Full article ">Figure 13
<p>Figure illustrating a connection between two perfect cells by a chain of bad-cell vertices and edges. Colors on the vertices and edges encode the values of the corresponding coefficients, where blue is for negative, red for positive, and gray is for near-zero, and the intensities of colors encode the magnitudes. The couplers of cell <math display="inline"><semantics> <msub> <mi>σ</mi> <mi>f</mi> </msub> </semantics></math> are all set to <math display="inline"><semantics> <mrow> <mo>−</mo> <mn>1</mn> </mrow> </semantics></math> forcing <math display="inline"><semantics> <msub> <mi>t</mi> <mn>12</mn> </msub> </semantics></math> and <math display="inline"><semantics> <msup> <mi>t</mi> <mo>*</mo> </msup> </semantics></math> to take the same values in an optimal solution.</p> Full article ">Figure 14
<p>Embedding of the Ising constraint <math display="inline"><semantics> <mrow> <msubsup> <mo>∑</mo> <mrow> <mi>i</mi> <mo>=</mo> <mn>1</mn> </mrow> <mi>n</mi> </msubsup> <msub> <mi>x</mi> <mi>i</mi> </msub> <mo>=</mo> <mo>−</mo> <mi>n</mi> <mo>+</mo> <mn>2</mn> </mrow> </semantics></math> (corresponding to QUBO constraint <math display="inline"><semantics> <mrow> <msubsup> <mo>∑</mo> <mrow> <mi>i</mi> <mo>=</mo> <mn>1</mn> </mrow> <mi>n</mi> </msubsup> <msub> <mi>x</mi> <mi>i</mi> </msub> <mo>=</mo> <mn>1</mn> </mrow> </semantics></math>) for <math display="inline"><semantics> <mrow> <mi>n</mi> <mo>=</mo> <mn>94</mn> </mrow> </semantics></math>. Colors encode vertex and edge values as in <a href="#algorithms-12-00077-f013" class="html-fig">Figure 13</a>.</p> Full article ">Figure 15
<p>Dependence of the quality of the constraint embedding measured as the value of the sum of all <math display="inline"><semantics> <msub> <mi>x</mi> <mi>i</mi> </msub> </semantics></math> (horizontal axis) on the value of the <span class="html-italic">gap</span> parameter, shown as curves of different colors. The vertical axis shows the frequency, or how many times, out of 10,000, the solution returned by the D-Wave annealer had the respective sum.</p> Full article ">Figure 16
<p>Dependence of the quality of the constraint embedding on the length of the vector <span class="html-italic">x</span> (number of problem variables <math display="inline"><semantics> <msub> <mi>x</mi> <mi>i</mi> </msub> </semantics></math>). Results for sizes <math display="inline"><semantics> <mrow> <mn>10</mn> <mo>,</mo> <mn>20</mn> <mo>,</mo> <mn>30</mn> <mo>,</mo> <mo>…</mo> <mo>,</mo> <mn>90</mn> </mrow> </semantics></math> are shown in different colors.</p> Full article ">Figure 17
<p>Illustration of our implementation for a vector <span class="html-italic">x</span> with 82 coordinates on a real D-Wave 2X hardware, which vector is constrained to contain exactly one <math display="inline"><semantics> <mrow> <mo>+</mo> <mn>1</mn> </mrow> </semantics></math> coordinate.</p> Full article ">Figure 18
<p>In this figure one can see how the dimension of <math display="inline"><semantics> <mi mathvariant="bold-italic">x</mi> </semantics></math> affects the accuracy of the embedding of the constraint, i.e., the number of <math display="inline"><semantics> <mrow> <mo>+</mo> <mn>1</mn> </mrow> </semantics></math> s in the resulting vector.</p> Full article ">
23 pages, 529 KiB  
Article
Programming Agents by Their Social Relationships: A Commitment-Based Approach
by Matteo Baldoni, Cristina Baroglio, Roberto Micalizio and Stefano Tedeschi
Algorithms 2019, 12(4), 76; https://doi.org/10.3390/a12040076 - 16 Apr 2019
Cited by 3 | Viewed by 4235
Abstract
Multiagent systems can be seen as an approach to software engineering for the design and development of complex, distributed software. Generally speaking, multiagent systems provide two main abstractions for modularizing the software: the agents and the environment where agents operate. In this paper, [...] Read more.
Multiagent systems can be seen as an approach to software engineering for the design and development of complex, distributed software. Generally speaking, multiagent systems provide two main abstractions for modularizing the software: the agents and the environment where agents operate. In this paper, we argue that also the social relationships among the agents should be expressed explicitly and become first-class objects both at design- and at development-time. In particular, we propose to represent social relationships as commitments that are reified as resources in the agents’ environment and can be directly manipulated by the agents via standard operations. We demonstrate that this view induces an agent programming schema that is substantially independent of the actual agent platform, provided that commitments are available as explained. The paper exemplifies the schema on two agent platforms, JADE and JaCaMo, where commitments are made available via the 2COMM library. Full article
(This article belongs to the Special Issue Social Computing and Multiagent Systems)
►▼ Show Figures

Figure 1

Figure 1
<p>Commitment life cycle [<a href="#B32-algorithms-12-00076" class="html-bibr">32</a>].</p> Full article ">Figure 2
<p>The logistic scenario.</p> Full article ">Figure 3
<p>The conceptual architecture of agents and their relationships.</p> Full article ">
10 pages, 8631 KiB  
Article
Pulmonary Fissure Detection in 3D CT Images Using a Multiple Section Model
by Runing Xiao and Jinzhi Zhou
Algorithms 2019, 12(4), 75; https://doi.org/10.3390/a12040075 - 15 Apr 2019
Cited by 4 | Viewed by 4360
Abstract
As a typical landmark in human lungs, the detection of pulmonary fissures is of significance to computer aided diagnosis and surgery. However, the automatic detection of pulmonary fissures in CT images is a difficult task due to complex factors like their 3D membrane [...] Read more.
As a typical landmark in human lungs, the detection of pulmonary fissures is of significance to computer aided diagnosis and surgery. However, the automatic detection of pulmonary fissures in CT images is a difficult task due to complex factors like their 3D membrane shape, intensity variation and adjacent interferences. Based on the observation that the fissure object often appears as thin curvilinear structures across 2D section images, we present an efficient scheme to solve this problem by merging the fissure line detection from multiple cross-sections in different directions. First, an existing oriented derivative of stick (ODoS) filter was modified for pulmonary fissure line enhancement. Then, an orientation partition scheme was applied to suppress the adhering clutters. Finally, a multiple section model was proposed for pulmonary fissure integration and segmentation. The proposed method is expected to improve fissure detection by extracting more weak objects while suppressing unrelated interferences. The performance of our scheme was validated in experiments using the publicly available open Lobe and Lung Analysis 2011 (LOLA11) dataset. Compared with manual references, the proposed scheme achieved a high segmentation accuracy, with a median F1-score of 0.8916, which was much better than conventional methods. Full article
►▼ Show Figures

Figure 1

Figure 1
<p>The principle of the derivative of stick (DoS) filter. Here, (<b>a</b>) denotes the orientation of the DoS filter, (<b>b</b>) depicts the responses of the DoS filter on typical pulmonary structures with the characters H, M and L indicate the high, moderate and low values, respectively. Note this figure is copied from [<a href="#B13-algorithms-12-00075" class="html-bibr">13</a>] with permission.</p> Full article ">Figure 2
<p>The orientation response of an oriented derivative of stick (ODoS) filter: (<b>a</b>) original image, (<b>b</b>) vector filed, (<b>c</b>) zoomed image of the red rectangle region in (<b>b</b>).</p> Full article ">Figure 3
<p>Improved orientation partition scheme.</p> Full article ">Figure 4
<p>Clutters suppression. (<b>a</b>) <span class="html-italic">N</span><sub>i</sub>. (<b>b</b>) <span class="html-italic">F</span><sup>A</sup>. (<b>c</b>) <span class="html-italic">F</span><sup>S</sup>. (<b>d</b>) <span class="html-italic">F</span><sup>C</sup>.</p> Full article ">Figure 5
<p>Investigate the shape feature of various pulmonary structures: (<b>a</b>) 3D visualization of a human lung, and its (<b>b</b>) sagittal slice, (<b>c</b>) coronal slice, (<b>d</b>) coronal slice.</p> Full article ">Figure 6
<p>A multiple section model.</p> Full article ">Figure 7
<p>Fissure segmentations, respectively, corresponding to (<b>a</b>) <span class="html-italic">F</span><sup>A</sup>, (<b>b</b>) <span class="html-italic">F</span><sup>S</sup>, (<b>c</b>) <span class="html-italic">F</span><sup>C</sup> and their integration (<b>d</b>).</p> Full article ">Figure 8
<p>3D fissure segmentation results from: (<b>a</b>) the proposed method, (<b>b</b>) the ODoS filter, (<b>c</b>) the DoS filter, and (<b>d</b>) the fissureness filter. Here, the cubes at the lower right corner indicate the view direction of the visualization in a standard anatomical coordinate system.</p> Full article ">Figure 9
<p>Quantitative validation of pulmonary fissure segmentation on the LOLA11 dataset using different methods. Here, the F1, FDR, FNR indices of five different methods are plotted from left to right, and the subscripts m5 and m4 represent the proposed method with the parameter <span class="html-italic">n</span> = 5 and 4. The subscripts od, d and f indicate the ODoS filter [<a href="#B14-algorithms-12-00075" class="html-bibr">14</a>], DoS filter and fissureness filter [<a href="#B7-algorithms-12-00075" class="html-bibr">7</a>], respectively.</p> Full article ">
23 pages, 5491 KiB  
Article
Bamboo Garden Trimming Problem: Priority Schedulings
by Mattia D’Emidio, Gabriele Di Stefano and Alfredo Navarra
Algorithms 2019, 12(4), 74; https://doi.org/10.3390/a12040074 - 13 Apr 2019
Cited by 6 | Viewed by 5785
Abstract
The paper deals with the Bamboo Garden Trimming (BGT) problem introduced in [Gąsieniec et al., SOFSEM’17]. The problem is difficult to solved due to its close relationship to Pinwheel scheduling. The garden with n bamboos is an analogue of a system of [...] Read more.
The paper deals with the Bamboo Garden Trimming (BGT) problem introduced in [Gąsieniec et al., SOFSEM’17]. The problem is difficult to solved due to its close relationship to Pinwheel scheduling. The garden with n bamboos is an analogue of a system of n machines that have to be attended (e.g., serviced) with different frequencies. During each day, bamboo b i grows an extra height h i , for i = 1 , … , n and, on the conclusion of the day, at most one bamboo has its entire height cut.The goal is to design a perpetual schedule of cuts to keep the height of the tallest ever bamboo as low as possible. The contribution in this paper is twofold, and is both theoretical and experimental. In particular, the focus is on understanding what has been called priority schedulings, i.e., cutting strategies where priority is given to bamboos whose current height is above a threshold greater than or equal to H = ∑ i = 1 n h i . Value H represents the total daily growth of the system and it is known that one cannot keep bamboos in the garden below this threshold indefinitely. As the first result, it is proved that, for any distribution of integer growth rates h 1 , … , h n and any priority scheduling, the system stabilises in a fixed cycle of cuts. Then, the focus is on the so-called ReduceMax strategy, a greedy priority scheduling that each day cuts the tallest bamboo, regardless of the growth rates distribution. ReduceMax is known to provide a O ( log n ) -approximation, with respect to the lower bound H. One of the main results achieved is that, if ReduceMax stabilises in a round-robin type cycle, then it guarantees 2-approximation. Furthermore, preliminary results are provided relating the structure of the input instance, in terms of growth rates, and the behavior of ReduceMax when applied to such inputs. Finally, a conjecture that ReduceMax is 2-approximating for the BGT problem is claimed, hence an extended experimental evaluation was conducted to support the conjecture and to compare ReduceMax with other relevant scheduling algorithms. The obtained results show that ReduceMax : (i) provides 2-approximation in all considered inputs; and (ii) always outperforms other considered strategies, even those for which better worst case approximation guarantees have been proven. Full article
(This article belongs to the Special Issue Algorithm Engineering: Towards Practically Efficient Solutions to Combinatorial Problems)
►▼ Show Figures

Figure 1

Figure 1
<p>An example of input instance for the Pinwheel problem where <math display="inline"><semantics> <mrow> <mi>V</mi> <mo>=</mo> <mo stretchy="false">(</mo> <mn>2</mn> <mo>,</mo> <mn>4</mn> <mo>,</mo> <mn>7</mn> <mo stretchy="false">)</mo> </mrow> </semantics></math> and hence <math display="inline"><semantics> <mrow> <mi>D</mi> <mo>=</mo> <mn>1</mn> <mo>/</mo> <mn>2</mn> <mo>+</mo> <mn>1</mn> <mo>/</mo> <mn>4</mn> <mo>+</mo> <mn>1</mn> <mo>/</mo> <mn>7</mn> <mo>≈</mo> <mn>0</mn> <mo>.</mo> <mn>89</mn> </mrow> </semantics></math>.</p> Full article ">Figure 2
<p>(<b>a</b>) Distribution of instances with respect to <span class="html-italic">n</span> for all partitions of integer <math display="inline"><semantics> <mrow> <mi>H</mi> <mo>∈</mo> <mo>{</mo> <mn>5</mn> <mo>,</mo> <mn>10</mn> <mo>,</mo> <mn>15</mn> <mo>,</mo> <mn>20</mn> <mo>,</mo> <mn>25</mn> <mo>,</mo> <mn>30</mn> <mo>,</mo> <mn>35</mn> <mo>}</mo> </mrow> </semantics></math>; and (<b>b</b>) distribution of instances with respect to <span class="html-italic">H</span> for all partitions of integer <math display="inline"><semantics> <mrow> <mi>H</mi> <mo>∈</mo> <mo>{</mo> <mn>5</mn> <mo>,</mo> <mn>10</mn> <mo>,</mo> <mn>15</mn> <mo>,</mo> <mn>20</mn> <mo>,</mo> <mn>25</mn> <mo>,</mo> <mn>30</mn> <mo>,</mo> <mn>35</mn> <mo>}</mo> </mrow> </semantics></math>.</p> Full article ">Figure 3
<p>Experiments conducted on all possible ordered instances obtained by setting <math display="inline"><semantics> <mrow> <mi>H</mi> <mo>=</mo> <mn>30</mn> </mrow> </semantics></math> and hence considering <span class="html-italic">n</span> varying in <math display="inline"><semantics> <mrow> <mo>{</mo> <mn>1</mn> <mo>,</mo> <mn>2</mn> <mo>,</mo> <mo>…</mo> <mo>,</mo> <mn>30</mn> <mo>}</mo> </mrow> </semantics></math>. Panels (<b>a</b>,<b>c</b>) refer to maximum <math display="inline"><semantics> <mrow> <mi>M</mi> <mo stretchy="false">(</mo> <mi>E</mi> <mo stretchy="false">)</mo> </mrow> </semantics></math>, whereas panels (<b>b</b>,<b>d</b>) refer to maximum <math display="inline"><semantics> <msub> <mi>λ</mi> <mi>E</mi> </msub> </semantics></math>. Panels (<b>c</b>,<b>d</b>) show strategies that, experimentally, exhibit 2-approximation.</p> Full article ">Figure 4
<p>Experiments conducted on all possible ordered instances obtained by setting <math display="inline"><semantics> <mrow> <mi>H</mi> <mo>=</mo> <mn>35</mn> </mrow> </semantics></math> and hence considering <span class="html-italic">n</span> varying in <math display="inline"><semantics> <mrow> <mo>{</mo> <mn>1</mn> <mo>,</mo> <mn>2</mn> <mo>,</mo> <mo>…</mo> <mo>,</mo> <mn>35</mn> <mo>}</mo> </mrow> </semantics></math>. Panels (<b>a</b>,<b>c</b>) refer to maximum <math display="inline"><semantics> <mrow> <mi>M</mi> <mo stretchy="false">(</mo> <mi>E</mi> <mo stretchy="false">)</mo> </mrow> </semantics></math>, whereas panels (<b>b</b>,<b>d</b>) refer to maximum <math display="inline"><semantics> <msub> <mi>λ</mi> <mi>E</mi> </msub> </semantics></math>. Panels (<b>c</b>,<b>d</b>) show strategies that, experimentally, exhibit 2-approximation.</p> Full article ">Figure 5
<p>Distribution of values of: <math display="inline"><semantics> <mrow> <mi>M</mi> <mo stretchy="false">(</mo> <mi>E</mi> <mo stretchy="false">)</mo> </mrow> </semantics></math> (<b>a</b>); and <math display="inline"><semantics> <msub> <mi>λ</mi> <mi>E</mi> </msub> </semantics></math> (<b>b</b>) exhibited by all algorithms on instances induced by all partitions of <math display="inline"><semantics> <mrow> <mi>H</mi> <mo>=</mo> <mn>35</mn> </mrow> </semantics></math>. Instances are sorted by non-decreasing values of: <math display="inline"><semantics> <mrow> <mi>M</mi> <mo stretchy="false">(</mo> <mi>E</mi> <mo stretchy="false">)</mo> </mrow> </semantics></math> (<b>a</b>); and <math display="inline"><semantics> <msub> <mi>λ</mi> <mi>E</mi> </msub> </semantics></math> (<b>b</b>). To magnify the differences, the <span class="html-italic">y</span>-axis in (<b>b</b>) is log-scaled.</p> Full article ">Figure 6
<p>Distribution of values of: <math display="inline"><semantics> <mrow> <mi>M</mi> <mo stretchy="false">(</mo> <mi>E</mi> <mo stretchy="false">)</mo> </mrow> </semantics></math> (<b>a</b>); <math display="inline"><semantics> <msub> <mi>λ</mi> <mi>E</mi> </msub> </semantics></math> (<b>b</b>); and number of days before stabilisation (<b>c</b>) as a function of <span class="html-italic">H</span>, for all considered strategies and instances.</p> Full article ">Figure 7
<p>How maximum <math display="inline"><semantics> <mrow> <mi>M</mi> <mo stretchy="false">(</mo> <mi>E</mi> <mo stretchy="false">)</mo> </mrow> </semantics></math> (<b>a</b>,<b>c</b>) and maximum <math display="inline"><semantics> <msub> <mi>λ</mi> <mi>E</mi> </msub> </semantics></math> (<b>b</b>,<b>d</b>) change as a function of <span class="html-italic">H</span> when instances are induced by all partitions of <math display="inline"><semantics> <mrow> <mi>H</mi> <mo>∈</mo> <mo>{</mo> <mn>10</mn> <mo>,</mo> <mn>15</mn> <mo>,</mo> <mn>20</mn> <mo>,</mo> <mn>25</mn> <mo>,</mo> <mn>30</mn> <mo>,</mo> <mn>35</mn> <mo>}</mo> </mrow> </semantics></math> having cardinality <math display="inline"><semantics> <mrow> <mi>n</mi> <mo>=</mo> <mn>10</mn> </mrow> </semantics></math>. Panels (<b>c</b>,<b>d</b>) show strategies that, experimentally, exhibit 2-approximation.</p> Full article ">Figure 8
<p>How maximum <math display="inline"><semantics> <mrow> <mi>M</mi> <mo stretchy="false">(</mo> <mi>E</mi> <mo stretchy="false">)</mo> </mrow> </semantics></math> (<b>a</b>) and maximum <math display="inline"><semantics> <msub> <mi>λ</mi> <mi>E</mi> </msub> </semantics></math> (<b>b</b>) change as a function of <span class="html-italic">H</span> when instances are induced by all partitions of <math display="inline"><semantics> <mrow> <mi>H</mi> <mo>∈</mo> <mo>{</mo> <mn>15</mn> <mo>,</mo> <mn>20</mn> <mo>,</mo> <mn>25</mn> <mo>,</mo> <mn>30</mn> <mo>,</mo> <mn>35</mn> <mo>}</mo> </mrow> </semantics></math> having cardinality <math display="inline"><semantics> <mrow> <mi>n</mi> <mo>=</mo> <mn>15</mn> </mrow> </semantics></math>. Panels (<b>c</b>,<b>d</b>) show strategies that, experimentally, exhibit 2-approximation.</p> Full article ">Figure 9
<p>Snapshot of the evolution of maximum heights when strategies: <math display="inline"><semantics> <mrow> <mi mathvariant="monospace">RMin</mi> </mrow> </semantics></math> (<b>a</b>); <math display="inline"><semantics> <mrow> <mi mathvariant="monospace">RMax</mi> </mrow> </semantics></math> (<b>b</b>); <math display="inline"><semantics> <msub> <mi mathvariant="monospace">RFast</mi> <mn>2</mn> </msub> </semantics></math> (<b>c</b>); and <math display="inline"><semantics> <msub> <mi mathvariant="monospace">RFast</mi> <mn>1</mn> </msub> </semantics></math> (<b>d</b>) are applied on an instance having <math display="inline"><semantics> <mrow> <mi>n</mi> <mo>=</mo> <mn>30</mn> </mrow> </semantics></math> and <math display="inline"><semantics> <mrow> <mi>H</mi> <mo>=</mo> <mn>70</mn> </mrow> </semantics></math>. (in details, structured as follows <math display="inline"><semantics> <mrow> <mo>[</mo> <mn>20</mn> <mo>;</mo> <mn>11</mn> <mo>;</mo> <mn>8</mn> <mo>;</mo> <mn>5</mn> <mo>;</mo> <mn>1</mn> <mo>;</mo> <mn>1</mn> <mo>;</mo> <mn>1</mn> <mo>;</mo> <mn>1</mn> <mo>;</mo> <mn>1</mn> <mo>;</mo> <mn>1</mn> <mo>;</mo> <mn>1</mn> <mo>;</mo> <mn>1</mn> <mo>;</mo> <mn>1</mn> <mo>;</mo> <mn>1</mn> <mo>;</mo> <mn>1</mn> <mo>;</mo> <mn>1</mn> <mo>;</mo> <mn>1</mn> <mo>;</mo> <mn>1</mn> <mo>;</mo> <mn>1</mn> <mo>;</mo> <mn>1</mn> <mo>;</mo> <mn>1</mn> <mo>;</mo> <mn>1</mn> <mo>;</mo> <mn>1</mn> <mo>;</mo> <mn>1</mn> <mo>;</mo> <mn>1</mn> <mo>;</mo> <mn>1</mn> <mo>;</mo> <mn>1</mn> <mo>;</mo> <mn>1</mn> <mo>;</mo> <mn>1</mn> <mo>;</mo> <mn>1</mn> <mo>]</mo> </mrow> </semantics></math>). On the <span class="html-italic">x</span>-axis the consecutive days are reported while on the <span class="html-italic">y</span>-axis the maximum height on the corresponding day is plot. The vertical line shows the beginning of the periodic phase while the horizontal lines show, respectively, <math display="inline"><semantics> <mrow> <mrow> <mo stretchy="false">(</mo> <mstyle displaystyle="true"> <munderover> <mo>∑</mo> <mrow> <mi>t</mi> <mo>=</mo> <mn>1</mn> </mrow> <msub> <mi>λ</mi> <mi>E</mi> </msub> </munderover> </mstyle> <msup> <mi>l</mi> <mi>t</mi> </msup> <mo stretchy="false">)</mo> </mrow> <mo>/</mo> <msub> <mi>λ</mi> <mi>E</mi> </msub> </mrow> </semantics></math> (i.e., <span class="html-italic">H</span>), <math display="inline"><semantics> <mrow> <mn>2</mn> <mi>H</mi> </mrow> </semantics></math>, <math display="inline"><semantics> <mrow> <mn>4</mn> <mi>H</mi> </mrow> </semantics></math>, and <math display="inline"><semantics> <mrow> <mi>M</mi> <mo stretchy="false">(</mo> <mi>E</mi> <mo stretchy="false">)</mo> </mrow> </semantics></math> over the entire execution.</p> Full article ">Figure 9 Cont.
<p>Snapshot of the evolution of maximum heights when strategies: <math display="inline"><semantics> <mrow> <mi mathvariant="monospace">RMin</mi> </mrow> </semantics></math> (<b>a</b>); <math display="inline"><semantics> <mrow> <mi mathvariant="monospace">RMax</mi> </mrow> </semantics></math> (<b>b</b>); <math display="inline"><semantics> <msub> <mi mathvariant="monospace">RFast</mi> <mn>2</mn> </msub> </semantics></math> (<b>c</b>); and <math display="inline"><semantics> <msub> <mi mathvariant="monospace">RFast</mi> <mn>1</mn> </msub> </semantics></math> (<b>d</b>) are applied on an instance having <math display="inline"><semantics> <mrow> <mi>n</mi> <mo>=</mo> <mn>30</mn> </mrow> </semantics></math> and <math display="inline"><semantics> <mrow> <mi>H</mi> <mo>=</mo> <mn>70</mn> </mrow> </semantics></math>. (in details, structured as follows <math display="inline"><semantics> <mrow> <mo>[</mo> <mn>20</mn> <mo>;</mo> <mn>11</mn> <mo>;</mo> <mn>8</mn> <mo>;</mo> <mn>5</mn> <mo>;</mo> <mn>1</mn> <mo>;</mo> <mn>1</mn> <mo>;</mo> <mn>1</mn> <mo>;</mo> <mn>1</mn> <mo>;</mo> <mn>1</mn> <mo>;</mo> <mn>1</mn> <mo>;</mo> <mn>1</mn> <mo>;</mo> <mn>1</mn> <mo>;</mo> <mn>1</mn> <mo>;</mo> <mn>1</mn> <mo>;</mo> <mn>1</mn> <mo>;</mo> <mn>1</mn> <mo>;</mo> <mn>1</mn> <mo>;</mo> <mn>1</mn> <mo>;</mo> <mn>1</mn> <mo>;</mo> <mn>1</mn> <mo>;</mo> <mn>1</mn> <mo>;</mo> <mn>1</mn> <mo>;</mo> <mn>1</mn> <mo>;</mo> <mn>1</mn> <mo>;</mo> <mn>1</mn> <mo>;</mo> <mn>1</mn> <mo>;</mo> <mn>1</mn> <mo>;</mo> <mn>1</mn> <mo>;</mo> <mn>1</mn> <mo>;</mo> <mn>1</mn> <mo>]</mo> </mrow> </semantics></math>). On the <span class="html-italic">x</span>-axis the consecutive days are reported while on the <span class="html-italic">y</span>-axis the maximum height on the corresponding day is plot. The vertical line shows the beginning of the periodic phase while the horizontal lines show, respectively, <math display="inline"><semantics> <mrow> <mrow> <mo stretchy="false">(</mo> <mstyle displaystyle="true"> <munderover> <mo>∑</mo> <mrow> <mi>t</mi> <mo>=</mo> <mn>1</mn> </mrow> <msub> <mi>λ</mi> <mi>E</mi> </msub> </munderover> </mstyle> <msup> <mi>l</mi> <mi>t</mi> </msup> <mo stretchy="false">)</mo> </mrow> <mo>/</mo> <msub> <mi>λ</mi> <mi>E</mi> </msub> </mrow> </semantics></math> (i.e., <span class="html-italic">H</span>), <math display="inline"><semantics> <mrow> <mn>2</mn> <mi>H</mi> </mrow> </semantics></math>, <math display="inline"><semantics> <mrow> <mn>4</mn> <mi>H</mi> </mrow> </semantics></math>, and <math display="inline"><semantics> <mrow> <mi>M</mi> <mo stretchy="false">(</mo> <mi>E</mi> <mo stretchy="false">)</mo> </mrow> </semantics></math> over the entire execution.</p> Full article ">Figure 10
<p>Snapshot of the evolution of maximum heights when strategies: <math display="inline"><semantics> <mrow> <mi mathvariant="monospace">RMin</mi> </mrow> </semantics></math> (<b>a</b>); <math display="inline"><semantics> <mrow> <mi mathvariant="monospace">RMax</mi> </mrow> </semantics></math> (<b>b</b>); <math display="inline"><semantics> <msub> <mi mathvariant="monospace">RFast</mi> <mn>2</mn> </msub> </semantics></math> (<b>c</b>); and <math display="inline"><semantics> <msub> <mi mathvariant="monospace">RFast</mi> <mn>1</mn> </msub> </semantics></math> (<b>d</b>) are applied on an instance having <math display="inline"><semantics> <mrow> <mi>n</mi> <mo>=</mo> <mn>30</mn> </mrow> </semantics></math> and <math display="inline"><semantics> <mrow> <mi>H</mi> <mo>=</mo> <mn>100</mn> </mrow> </semantics></math> (in details, structured as follows <math display="inline"><semantics> <mrow> <mo>[</mo> <mn>70</mn> <mo>;</mo> <mn>2</mn> <mo>;</mo> <mn>1</mn> <mo>;</mo> <mn>1</mn> <mo>;</mo> <mn>1</mn> <mo>;</mo> <mn>1</mn> <mo>;</mo> <mn>1</mn> <mo>;</mo> <mn>1</mn> <mo>;</mo> <mn>1</mn> <mo>;</mo> <mn>1</mn> <mo>;</mo> <mn>1</mn> <mo>;</mo> <mn>1</mn> <mo>;</mo> <mn>1</mn> <mo>;</mo> <mn>1</mn> <mo>;</mo> <mn>1</mn> <mo>;</mo> <mn>1</mn> <mo>;</mo> <mn>1</mn> <mo>;</mo> <mn>1</mn> <mo>;</mo> <mn>1</mn> <mo>;</mo> <mn>1</mn> <mo>;</mo> <mn>1</mn> <mo>;</mo> <mn>1</mn> <mo>;</mo> <mn>1</mn> <mo>;</mo> <mn>1</mn> <mo>;</mo> <mn>1</mn> <mo>;</mo> <mn>1</mn> <mo>;</mo> <mn>1</mn> <mo>;</mo> <mn>1</mn> <mo>;</mo> <mn>1</mn> <mo>;</mo> <mn>1</mn> <mo>]</mo> </mrow> </semantics></math>). Data are plotted as in <a href="#algorithms-12-00074-f009" class="html-fig">Figure 9</a>.</p> Full article ">Figure 11
<p>Snapshot of the evolution of maximum heights when strategies: <math display="inline"><semantics> <mrow> <mi mathvariant="monospace">RMin</mi> </mrow> </semantics></math> (<b>a</b>); <math display="inline"><semantics> <mrow> <mi mathvariant="monospace">RMax</mi> </mrow> </semantics></math> (<b>b</b>); <math display="inline"><semantics> <msub> <mi mathvariant="monospace">RFast</mi> <mn>2</mn> </msub> </semantics></math> (<b>c</b>); and <math display="inline"><semantics> <msub> <mi mathvariant="monospace">RFast</mi> <mn>1</mn> </msub> </semantics></math> (<b>d</b>) are applied on an instance having <math display="inline"><semantics> <mrow> <mi>n</mi> <mo>=</mo> <mn>10</mn> </mrow> </semantics></math> and <math display="inline"><semantics> <mrow> <mi>H</mi> <mo>=</mo> <mn>40</mn> </mrow> </semantics></math> (in details, structured as follows <math display="inline"><semantics> <mrow> <mo>[</mo> <mn>15</mn> <mo>;</mo> <mn>13</mn> <mo>;</mo> <mn>4</mn> <mo>;</mo> <mn>2</mn> <mo>;</mo> <mn>1</mn> <mo>;</mo> <mn>1</mn> <mo>;</mo> <mn>1</mn> <mo>;</mo> <mn>1</mn> <mo>;</mo> <mn>1</mn> <mo>;</mo> <mn>1</mn> <mo>]</mo> </mrow> </semantics></math>). Data are plotted as in <a href="#algorithms-12-00074-f009" class="html-fig">Figure 9</a>.</p> Full article ">Figure 12
<p>Snapshot of the evolution of maximum heights when strategies: <math display="inline"><semantics> <mrow> <mi mathvariant="monospace">RMin</mi> </mrow> </semantics></math> (<b>a</b>); <math display="inline"><semantics> <mrow> <mi mathvariant="monospace">RMax</mi> </mrow> </semantics></math> (<b>b</b>); <math display="inline"><semantics> <msub> <mi mathvariant="monospace">RFast</mi> <mn>2</mn> </msub> </semantics></math> (<b>c</b>); and <math display="inline"><semantics> <msub> <mi mathvariant="monospace">RFast</mi> <mn>1</mn> </msub> </semantics></math> (<b>d</b>) are applied on an instance having <math display="inline"><semantics> <mrow> <mi>n</mi> <mo>=</mo> <mn>10</mn> </mrow> </semantics></math> and <math display="inline"><semantics> <mrow> <mi>H</mi> <mo>=</mo> <mn>200</mn> </mrow> </semantics></math> (in details, structured as follows <math display="inline"><semantics> <mrow> <mo>[</mo> <mn>61</mn> <mo>;</mo> <mn>30</mn> <mo>;</mo> <mn>27</mn> <mo>;</mo> <mn>26</mn> <mo>;</mo> <mn>13</mn> <mo>;</mo> <mn>11</mn> <mo>;</mo> <mn>10</mn> <mo>;</mo> <mn>10</mn> <mo>;</mo> <mn>9</mn> <mo>;</mo> <mn>3</mn> <mo>]</mo> </mrow> </semantics></math>). Data are plotted as in <a href="#algorithms-12-00074-f009" class="html-fig">Figure 9</a>.</p> Full article ">
20 pages, 1984 KiB  
Article
Permuted Pattern Matching Algorithms on Multi-Track Strings
by Diptarama Hendrian, Yohei Ueki, Kazuyuki Narisawa, Ryo Yoshinaka and Ayumi Shinohara
Algorithms 2019, 12(4), 73; https://doi.org/10.3390/a12040073 - 8 Apr 2019
Cited by 3 | Viewed by 5484
Abstract
A multi-track string is a tuple of strings of the same length. Given the pattern and text of two multi-track strings, the permuted pattern matching problem is to find the occurrence positions of all permutations of the pattern in the text. In this [...] Read more.
A multi-track string is a tuple of strings of the same length. Given the pattern and text of two multi-track strings, the permuted pattern matching problem is to find the occurrence positions of all permutations of the pattern in the text. In this paper, we propose several algorithms for permuted pattern matching. Our first algorithm, which is based on the Knuth–Morris–Pratt (KMP) algorithm, has a fast theoretical computing time with O ( m k ) as the preprocessing time and O ( n k log σ ) as the matching time, where n, m, k, σ , and occ denote the length of the text, the length of the pattern, the number of strings in the multi-track, the alphabet size, and the number of occurrences of the pattern, respectively. We then improve the KMP-based algorithm by using an automaton, which has a better experimental running time. The next proposed algorithms are based on the Boyer–Moore algorithm and the Horspool algorithm that try to perform pattern matching. These algorithms are the fastest experimental algorithms. Furthermore, we propose an extension of the AC-automaton algorithm that can solve dictionary matching on multi-tracks, which is a task to find multiple multi-track patterns in a multi-track text. Finally, we propose filtering algorithms that can perform permuted pattern matching quickly in practice. Full article
(This article belongs to the Special Issue String Matching and Its Applications)
►▼ Show Figures

Figure 1

Figure 1
<p>The multi-track AC-automaton <math display="inline"><semantics> <mrow> <mi mathvariant="sans-serif">MTAC</mi> <mo>(</mo> <mi>D</mi> <mo>)</mo> </mrow> </semantics></math> for <math display="inline"><semantics> <mrow> <mi>D</mi> <mo>=</mo> <mo>{</mo> <msub> <mi mathvariant="double-struck">P</mi> <mn>1</mn> </msub> <mo>,</mo> <msub> <mi mathvariant="double-struck">P</mi> <mn>2</mn> </msub> <mo>,</mo> <msub> <mi mathvariant="double-struck">P</mi> <mn>3</mn> </msub> <mo>}</mo> </mrow> </semantics></math>, where <math display="inline"><semantics> <mrow> <msub> <mi mathvariant="double-struck">P</mi> <mn>1</mn> </msub> <mo>=</mo> <mfenced separators="" open="(" close=")"> <mi mathvariant="monospace">aaabb</mi> <mo>,</mo> <mi mathvariant="monospace">abaab</mi> <mo>,</mo> <mi mathvariant="monospace">bbaaa</mi> </mfenced> </mrow> </semantics></math>, <math display="inline"><semantics> <mrow> <msub> <mi mathvariant="double-struck">P</mi> <mn>2</mn> </msub> <mo>=</mo> <mfenced separators="" open="(" close=")"> <mi mathvariant="monospace">abab</mi> <mo>,</mo> <mi mathvariant="monospace">abba</mi> <mo>,</mo> <mi mathvariant="monospace">bbab</mi> </mfenced> </mrow> </semantics></math>, and <math display="inline"><semantics> <mrow> <msub> <mi mathvariant="double-struck">P</mi> <mn>3</mn> </msub> <mo>=</mo> <mfenced separators="" open="(" close=")"> <mi mathvariant="monospace">aabbab</mi> <mo>,</mo> <mi mathvariant="monospace">bababb</mi> <mo>,</mo> <mi mathvariant="monospace">baaaab</mi> </mfenced> </mrow> </semantics></math>. The asterisk “*” is a special symbol that matches any symbol in <math display="inline"><semantics> <mo>Σ</mo> </semantics></math>.</p> Full article ">Figure 2
<p>The multi-track permuted matching automaton <math display="inline"><semantics> <mrow> <mi mathvariant="sans-serif">MTPMA</mi> <mo>(</mo> <mi mathvariant="double-struck">P</mi> <mo>)</mo> </mrow> </semantics></math> for <math display="inline"><semantics> <mrow> <mi mathvariant="double-struck">P</mi> <mo>=</mo> <mfenced separators="" open="(" close=")"> <mi mathvariant="monospace">aaabb</mi> <mo>,</mo> <mi mathvariant="monospace">abaab</mi> <mo>,</mo> <mi mathvariant="monospace">bbaaa</mi> </mfenced> </mrow> </semantics></math>. The asterisk is a special symbol that matches with any symbols in <math display="inline"><semantics> <mo>Σ</mo> </semantics></math>.</p> Full article ">Figure 3
<p>(<b>a</b>) Track trie of <math display="inline"><semantics> <mrow> <mi mathvariant="double-struck">P</mi> <mo>=</mo> <mo>(</mo> <mi mathvariant="monospace">bbaba</mi> <mo>,</mo> <mi mathvariant="monospace">abbba</mi> <mo>,</mo> <mi mathvariant="monospace">aaabb</mi> <mo>)</mo> </mrow> </semantics></math>; (<b>b</b>) example of mismatch when the track trie cannot find the transition; (<b>c</b>) example of mismatch when the number of tracks is more than the weight of the node.</p> Full article ">Figure 4
<p>Running time of the multi-track KMP (MTKMP), multi-track AC-automaton (MTACA), multi-track permuted matching automaton (MTPMA) algorithms on permuted pattern matching with respect to (<b>a</b>) the text length, (<b>b</b>) the track count, (<b>c</b>) the pattern length, and (<b>d</b>) the alphabet size.</p> Full article ">Figure 5
<p>Running time of the multi-track Buyer–Moore (MTBM) and multi-track Horspool (MTH) algorithms on permuted pattern matching with respect to (<b>a</b>) the text length, (<b>b</b>) the track count, (<b>c</b>) the pattern length, and (<b>d</b>) the alphabet size.</p> Full article ">Figure 6
<p>Running time of the filtering algorithms (Knuth–Morris–Pratt (Filter-KMP), Boyer–Moore (Filter-BM), and Horspool (Filter-H)) for permuted pattern matching with respect to (<b>a</b>) the text length, (<b>b</b>) the track count, (<b>c</b>) the pattern length, and (<b>d</b>) the alphabet size.</p> Full article ">Figure 6 Cont.
<p>Running time of the filtering algorithms (Knuth–Morris–Pratt (Filter-KMP), Boyer–Moore (Filter-BM), and Horspool (Filter-H)) for permuted pattern matching with respect to (<b>a</b>) the text length, (<b>b</b>) the track count, (<b>c</b>) the pattern length, and (<b>d</b>) the alphabet size.</p> Full article ">Figure 7
<p>Comparison of the running time of the AC-automaton-based algorithm with the proposed algorithms for permuted pattern matching with respect to (<b>a</b>) the text length, (<b>b</b>) the track count, (<b>c</b>) the pattern length, and (<b>d</b>) the alphabet size.</p> Full article ">
12 pages, 1581 KiB  
Article
An Improved ABC Algorithm and Its Application in Bearing Fault Diagnosis with EEMD
by Weijia Chen and Yancai Xiao
Algorithms 2019, 12(4), 72; https://doi.org/10.3390/a12040072 - 4 Apr 2019
Cited by 16 | Viewed by 5235
Abstract
The Ensemble Empirical Mode Decomposition (EEMD) algorithm has been used in bearing fault diagnosis. In order to overcome the blindness in the selection of white noise amplitude coefficient e in EEMD, an improved artificial bee colony algorithm (IABC) is proposed to obtain it [...] Read more.
The Ensemble Empirical Mode Decomposition (EEMD) algorithm has been used in bearing fault diagnosis. In order to overcome the blindness in the selection of white noise amplitude coefficient e in EEMD, an improved artificial bee colony algorithm (IABC) is proposed to obtain it adaptively, which providing a new idea for the selection of EEMD parameters. In the improved algorithm, chaos initialization is introduced in the artificial bee colony (ABC) algorithm to insure the diversity of the population and the ergodicity of the population search process. On the other hand, the collecting bees are divided into two parts in the improved algorithm, one part collects the optimal information of the region according to the original algorithm, the other does Levy flight around the current global best solution to improve its global search capabilities. Four standard test functions are used to show the superiority of the proposed method. The application of the IABC and EEMD algorithm in bearing fault diagnosis proves its effectiveness. Full article
►▼ Show Figures

Figure 1

Figure 1
<p>Principle of the Improved Artificial Bee Colony Algorithm.</p> Full article ">Figure 2
<p>Evolution curve of each function. (<b>a</b>) Sphere function; (<b>b</b>) Rosenbrock function; (<b>c</b>) Griewank function; and (<b>d</b>) Ackley function.</p> Full article ">Figure 2 Cont.
<p>Evolution curve of each function. (<b>a</b>) Sphere function; (<b>b</b>) Rosenbrock function; (<b>c</b>) Griewank function; and (<b>d</b>) Ackley function.</p> Full article ">Figure 3
<p>The experimental setup.</p> Full article ">Figure 4
<p>The Fourier transform spectrum of the IMF component with the maximum kurtosis.</p> Full article ">Figure 5
<p>The Fourier transform spectrum of original signal.</p> Full article ">
22 pages, 1398 KiB  
Article
Parameter Combination Framework for the Differential Evolution Algorithm
by Jinghua Zhang and Ze Dong
Algorithms 2019, 12(4), 71; https://doi.org/10.3390/a12040071 - 2 Apr 2019
Cited by 4 | Viewed by 4777
Abstract
The differential evolution (DE) algorithm is a popular and efficient evolutionary algorithm that can be used for single objective real-parameter optimization. Its performance is greatly affected by its parameters. Generally, parameter control strategies involve determining the most suitable value for the current state; [...] Read more.
The differential evolution (DE) algorithm is a popular and efficient evolutionary algorithm that can be used for single objective real-parameter optimization. Its performance is greatly affected by its parameters. Generally, parameter control strategies involve determining the most suitable value for the current state; there is only a little research on parameter combination and parameter distribution which is also useful for improving algorithm performance. This paper proposes an idea to use parameter region division and parameter strategy combination to flexibly adjust the parameter distribution. Based on the idea, a group-based two-level parameter combination framework is designed to support various modes of parameter combination, and enrich the parameter distribution characteristics. Under this framework, two customized parameter combination strategies are given for a single-operation DE algorithm and a multi-operation DE algorithm. The experiments verify the effectiveness of the two strategies and it also illustrates the meaning of the framework. Full article
►▼ Show Figures

Figure 1

Figure 1
<p>Individual and parameters distribution maps of three parameter strategies for f1: (<b>a</b>) random strategy; (<b>b</b>) jDE strategy; and (<b>c</b>) SHADE strategy.</p> Full article ">Figure 2
<p>Individual and parameter distribution maps of three parameter strategies for f2: (<b>a</b>) random strategy; (<b>b</b>) jDE strategy; and (<b>c</b>) SHADE strategy.</p> Full article ">Figure 3
<p>Parameter region division.</p> Full article ">Figure 4
<p>Grouping based two-level parameter combination scheme.</p> Full article ">Figure 5
<p>The process of parameter distribution (F*CR) variation for f12 (50D).</p> Full article ">
13 pages, 1501 KiB  
Article
Task Assignment of the Improved Contract Net Protocol under a Multi-Agent System
by Jiarui Zhang, Gang Wang and Yafei Song
Algorithms 2019, 12(4), 70; https://doi.org/10.3390/a12040070 - 1 Apr 2019
Cited by 18 | Viewed by 5403
Abstract
Background: The existing contract net protocol has low overall efficiency during the bidding and release period, and a large amount of redundant information is generated during the negotiation process. Methods: On the basis of an ant colony algorithm, the dynamic response threshold model [...] Read more.
Background: The existing contract net protocol has low overall efficiency during the bidding and release period, and a large amount of redundant information is generated during the negotiation process. Methods: On the basis of an ant colony algorithm, the dynamic response threshold model and the flow of pheromone model were established, then the complete task allocation process was designed. Three experimental settings were simulated under different conditions. Results: When the number of agents was 20 and the maximum load value was L max = 3 , the traffic and run-time of task allocation under the improved contract net protocol decreased. When the number of tasks and L max was fixed, the improved contract net protocol had advantages over the dynamic contract net and classical contract net protocols in terms of both traffic and run-time. Setting up the number of agents, tasks and L max to improve the task allocation under the contract net not only minimizes the number of errors, but also the task completion rate reaches 100%. Conclusions: The improved contract net protocol can reduce the traffic and run-time compared with classical contract net and dynamic contract net protocols. Furthermore, the algorithm can achieve better assignment results and can re-forward all erroneous tasks. Full article
(This article belongs to the Special Issue Social Computing and Multiagent Systems)
►▼ Show Figures

Figure 1

Figure 1
<p>Agent basic structure.</p> Full article ">Figure 2
<p>The flow of pheromones.</p> Full article ">Figure 3
<p>Improving the contract net protocol process.</p> Full article ">Figure 4
<p>Unified Modeling Language (UML) class diagram of manager agent and contractor agent.</p> Full article ">Figure 5
<p>Quantitative analysis with different task numbers. (<b>a</b>) The traffic of the improved contract net protocol with different numbers of tasks; (<b>b</b>) The run-time of the improved contract net protocol with different numbers of tasks.</p> Full article ">Figure 6
<p>Comparative analysis of the three algorithms with different agent numbers. (<b>a</b>) The traffic of the improved contract net protocol with a different number of tasks; (<b>b</b>) The run-time of the improved contract net protocol with a different number of tasks.</p> Full article ">Figure 7
<p>Task allocation of 30 agents under three algorithms.</p> Full article ">
2 pages, 129 KiB  
Editorial
Special Issue on Algorithms in Computational Finance
by V L Raju Chinthalapati and Edward Tsang
Algorithms 2019, 12(4), 69; https://doi.org/10.3390/a12040069 - 31 Mar 2019
Cited by 2 | Viewed by 4430
Abstract
Algorithms play an important part in finance [...] Full article
(This article belongs to the Special Issue Algorithms in Computational Finance)
21 pages, 937 KiB  
Article
A Cross-Layer Optimization QoS Scheme in Wireless Multimedia Sensor Networks
by Shu Fan
Algorithms 2019, 12(4), 68; https://doi.org/10.3390/a12040068 - 30 Mar 2019
Cited by 4 | Viewed by 4637
Abstract
There are two main challenges in wireless multimedia sensors networks: energy constraints and providing DiffServ. In this paper, a joint flow control, routing, scheduling, and power control scheme based on a Lyapunov optimization framework is proposed to increase network lifetime and scheduling fairness. [...] Read more.
There are two main challenges in wireless multimedia sensors networks: energy constraints and providing DiffServ. In this paper, a joint flow control, routing, scheduling, and power control scheme based on a Lyapunov optimization framework is proposed to increase network lifetime and scheduling fairness. For an adaptive distribution of transmission opportunities, a differentiated queueing services (DQS) scheme is adopted for maintaining data queues. In the Lyapunov function, different types of queues are normalized for a unified dimension. To prolong network lifetime, control coefficients are designed according to the characteristics of the wireless sensor networks. The power control problem is proved to be a convex optimization problem and two optimal algorithms are discussed. Simulation results show that, compared with existing schemes, the proposed scheme can achieve a better trade-off between QoS performances and network lifetime. The simulation results also show that the scheme utilizing the distributed media access control scheme in scheduling performs best in the transmission of real-time services. Full article
(This article belongs to the Special Issue Recent Advances in Nonsmooth Optimization and Analysis)
►▼ Show Figures

Figure 1

Figure 1
<p>Stability period with varying number of nodes.</p> Full article ">Figure 2
<p>Consumed power of the network with varying number of nodes.</p> Full article ">Figure 3
<p>Comparison of the ratio of survival nodes in the region of radius R.</p> Full article ">Figure 4
<p>Comparison of the ratio of survival nodes out of region of radius R.</p> Full article ">Figure 5
<p>Average throughput of real-time sessions under different number of nodes.</p> Full article ">Figure 6
<p>Average throughput of non-real-time sessions under different number of nodes.</p> Full article ">Figure 7
<p>Average end-to-end delay of real-time sessions under different numbers of nodes.</p> Full article ">Figure 8
<p>Average end-to-end delay of non-real-time sessions under different numbers of nodes.</p> Full article ">Figure 9
<p>Network lifetime.</p> Full article ">Figure 10
<p>Average number of packets of non-real-time services arriving at the sink node.</p> Full article ">Figure 11
<p>Average number of packets of real-time services arriving at the sink node.</p> Full article ">
15 pages, 919 KiB  
Article
A Two-Phase Approach for Single Container Loading with Weakly Heterogeneous Boxes
by Rommel Dias Saraiva, Napoleão Nepomuceno and Plácido Rogério Pinheiro
Algorithms 2019, 12(4), 67; https://doi.org/10.3390/a12040067 - 30 Mar 2019
Cited by 10 | Viewed by 5003
Abstract
We propose in this paper a two-phase approach that decomposes the process of solving the three-dimensional single Container Loading Problem (CLP) into subsequent tasks: (i) the generation of blocks of boxes and (ii) the loading of blocks into the container. The first phase [...] Read more.
We propose in this paper a two-phase approach that decomposes the process of solving the three-dimensional single Container Loading Problem (CLP) into subsequent tasks: (i) the generation of blocks of boxes and (ii) the loading of blocks into the container. The first phase is deterministic, and it is performed by means of constructive algorithms from the literature. The second phase is non-deterministic, and it is performed with the use of Generate-and-Solve (GS), a problem-independent hybrid optimization framework based on problem instance reduction that combines a metaheuristic with an exact solver. Computational experiments performed on benchmark instances indicate that our approach presents competitive results compared to those found by state-of-the-art algorithms, particularly for problem instances consisting of a few types of boxes. In fact, we present new best solutions for classical instances from groups BR1 and BR2. Full article
(This article belongs to the Special Issue Metaheuristic Algorithms in Optimization and Applications (volume 2))
►▼ Show Figures

Figure 1

Figure 1
<p>A container loading pattern with orientation and stability constraints.</p> Full article ">Figure 2
<p>A simple block with four boxes in a row, two boxes in a column, and three boxes in a stack.</p> Full article ">Figure 3
<p>A guillotine block obtained from the combination of two simple blocks.</p> Full article ">Figure 4
<p>A representation of a guillotine block, its MBC, and the residual space on top of it.</p> Full article ">Figure 5
<p>The generate-and-solve hybrid framework.</p> Full article ">Figure 6
<p>Chromosome of random keys.</p> Full article ">
Show export options expand_more Show export options expand_less
Select all
Export citation of selected articles as:
 
Displaying articles 1-21
Previous Issue
Next Issue
Back to TopTop