1 Introduction

The superyacht industry is an increasingly valuable market and an attractive business. As of July 2011, the superyacht market has grown by 43 %, and the wide range of mid-sized superyachts shares 70 % of the market [1]. Up to now, most superyachts have been built in Europe, where the advanced shipbuilding countries like Italy, Netherlands, United Kingdom, and Germany dominate the passenger ship market. Korea and China, on the other hand, have not actively participated in this business, choosing to focus on the production of commercial vessels in which they dominate. As a result, they fall behind in design and technology stressed in the luxurious interior design of superyachts.

The conceptual design of superyachts pursues a different direction unlike the commercial vessels that are well equipped with modern technology and advanced engineering analyses. Systematic research has not been carried out and therefore such publications are very rare.

An approach to determine a preliminary hull form of superyachts was published by Nam et al. [2]. They focused on the construction of a hull form by the analysis of previously built ships. Lee and Byun [3] suggested that the analysis of deck layout could lead the designer towards a systematic way of modern design. They also mentioned that, with no universal concept or guidelines, most interior design works were executed by experts in advanced shipbuilding countries.

In regards to the determination of space, a trial attempt for performing an interior space arrangement using the genetic algorithm was introduced, where they tried to convert the design concept into an engineering analysis problem [4]. Lee et al. [5] suggested that the problem of compartment layout could be improved by using the genetic algorithm. They included the multi-deck constraint but did not take the stairs into consideration in spite of their important role in space arrangement. Other efforts for the optimization of general arrangement of ships were made by Parsons et al. [6] and updated by Daniels et al. [7]. They had a number of compartments to be arranged but treated each deck separately without considering the connectivity between decks.

Evolutionary algorithms, including the genetic algorithm (GA, hereafter), have been recognized as being efficient in solving complicated optimization problems. The concept of GA was invented by John Holland at the University of Michigan in the 1960s and popularized by Goldberg [8]. The GA is a method for moving one population (strings or genes) to a new one by using a kind of “natural selection” together with crossover and mutation processes. Design variables required in determining the interior arrangement are treated as constraints that are combined with the GA. In this paper, the GA is adopted as a primary solver since our problem can be regarded as a variant of a multi-objective problem.

The main contribution of this research is to propose a method of determining space arrangement based on a constraint-based genetic algorithm (CBGA). This approach allows constraints to be added according to specified requirements and a client’s preferences [9, 10]. Section 2 explains the fundamental concept and the mathematical formulation required for the optimization of interior space arrangement. Various mechanisms of genetic algorithm such as encoding, evaluation, production, crossover, and mutation are applied to the proposed CBGA in Sect. 3. Section 4 discusses the results of space arrangement examples performed for different designer’s requirements.

2 Formulation of space arrangement problem

In the stage of conceptual design, the designer establishes major characteristics of a ship without violating technical requirements, which is normally challenging and complicated. In addition, he or she has to satisfy all technical and aesthetical expectations of the client, who usually has many requests that may be conflicting with the designer’s guideline. This situation becomes critical and sometimes even controversial in designing the interior space arrangement in which no specific engineering formulas exist. The feasible solution is normally obtained by compromising the client’s expectations and the designer’s restrictions. The expectations of the client and the engineering restrictions faced by the designer result in a complicated and nonlinear formulation in which a number of objective functions with design variables and constraints are involved. This kind of problem can be regarded as a complex example of multi-objective functions.

Our space arrangement problem involves multiple, contradictory, and mostly subjective requirements, such as confliction due to the irregular shapes of neighboring spaces and their locations. To reflect all the multiple yet conflicting requirements, it is suggested that the problem should be formulated as a variant of a multi-objective function, which can be achieved by converting the effect of multi-objectives to a single value constructed using weight factors normalized.

2.1 Problem formulation of multi-deck space arrangement

The space arrangement problem, in the form of a general multi-objective problem, can be defined as Eq. (1):

$$ {\text{Optimize }}F(x) = [F_{\text{Space}} (x),F_{\text{Sub}} (x),F_{\text{Stair}} (x)],\:{\text{subject}}\;{\text{to}}\;g_{j} (x),\quad j = 1,2, \ldots m, $$
(1)

where x is the design variables, g j (x) is a set of inequality constraints, and m is the number of constraints. Each objective function has its role in the optimization process. The first two functions, F Space and F Sub, relating to the area requirement are defined by:

$$ \begin{aligned} F_{\text{Space}} & = \frac{{|A_{\text{C}} - A_{\text{lower}} | + |A_{\text{C}} - A_{\text{upper}} |}}{{A_{\text{Deck}} }}\,{\text{and}} \\ F_{\text{Sub}} \, & = \frac{{|A_{\text{Sub}} - A_{{{\text{Sub\_lower}}}} | + |A_{\text{Sub}} - {\text{A}}_{{{\text{Sub\_upper}}}} |}}{{A_{\text{Deck}} }} \\ \end{aligned}, $$
(2)

where A Deck, A C, and A Sub are the area of a deck, a main space, and a subordinate space, respectively. The subscripts, lower and upper, represent the lower and upper limits of the corresponding area and they are defined by the user’s preference. Detailed descriptions of those spaces will be made later. The objective functions, F Space and F Sub are the sub-fitness values in the percentage of space occupancy of a certain compartment compared to the maximum area of a deck.

On the other hand, F Stair is the sub-fitness value in the ratio of stair distance obtained to the longest distance in each deck, as illustrated in Fig. 1.

Fig. 1
figure 1

Definition of fitness value for stairs

Full size image

Our goal is to minimize the sum of stair distance while optimizing the area of space within the client’s preferences or expert’s requirements. The objective function possesses conflicting goals and constraints like the ordinary multi-objective optimization problems.

To solve the problem, we assume that each deck is represented by 40 × 11 equally sized grids, following our previous work [4]. This assumption comes from the analysis of the current design of general mid-sized superyachts that approximately have the length of 40 m and the width of 11 m. The number of grids is flexible and can be defined differently in the beginning stage. The design variables, shown in Eq. (1), are supposed to define spaces and are assumed to represent the two dimensional coordinates of spaces on the deck. To accelerate the calculation of the objective function, all values are encoded in integers rather than in binary. Thus, the design variables are real coded values in our CBGA, which means the chromosome in GA will be an integer rather than binary or floating.

2.2 Formulation as sum of weighted factors

It is important to choose a good objective function in applying the CBGA to a problem. It can have a set of multiple components but should be represented as a combined numeral value. Important design factors such as space occupancy, shape of spaces, and stair connectivity are taken into consideration in determining an optimal layout of spaces in this work. Each factor emphasizes the importance of its own role. It would be more plausible, however, to combine and reasonably balance out the three factors.

The fitness value, F, in Eq. (3), chosen as an objective function, is assumed to be the weighted average of the defined design factors. In our research, the combination of these factors is formulated as a function of a set of dominant factors determining the space allocation such as space area, stair distance, and shape constraint of space:

$$ F = \frac{{w_{\text{Space}} F_{\text{Space}} + w_{\text{Stair}} F_{\text{Stair}} + w_{\text{Sub}} F_{\text{Sub}} g_{\text{Shape}} }}{{w_{\text{Space}} + w_{\text{Stair}} + w_{\text{Sub}} }} + \sum\limits_{j} {g_{j} (x)}. $$
(3)

The weighting factors balancing the three sub-values w Space, w Stair, and w Sub, should be defined by the designer in the beginning stage and are set between 0 and 1. It should be noted that other factors could be added upon the request of the owner or the designer. The constraint function g j (x) is considered as a penalty function, as discussed in the coming section.

3 Constraint-based GA application for space arrangement

The aim of this work is to suggest a "good"initial space arrangement for the designer and the client so that they are able to not only reduce the time that might have been devoted to manual design, but also consider various arrangements previously unconsidered. A typical design procedure includes the compromise between different layouts. With a set of good layouts in hand, it becomes much easier to reach a final decision. It should be noted that the proposed algorithm for the space arrangement, as described in Fig. 2, is meant to suggest a probable and reasonable solution rapidly and is subject to a so-called tuning process for a final arrangement.

Fig. 2
figure 2

A design procedure for interior space arrangement

Full size image

A previous approach to find an optimal space arrangement of a superyacht established an objective value of space arrangement that considered rectangular space, connecting information between the two spaces via stairs [4]. Even though they applied a GA technique, the results were not fully satisfactory because of its limitations in shape and inefficient convergence, partly caused by the inappropriate application of the GA. This limitation has to be resolved for the practical application of the algorithm.

A modified and improved technique is introduced here. A set of design constraints is simultaneously considered in the problem formulation. These constraints are incorporated to establish a new constraint-based genetic algorithm (CBGA) that automatically determines the arrangement of various irregular-shaped spaces and stairs. Other constraints are free to be added if necessary.

3.1 Major constrained elements

Every space is basically assumed to be rectangular, defined as MAIN space in this work. The idea of using equally sized grids in each deck is efficient for the definition of each space. Then, a space can be represented by the (x, y) coordinates of a corner point and by its width and height.

The concept of SUB space is significant to consider for the irregular shape of spaces in real superyachts. The SUB is defined as a sub-compartment connected to a MAIN, as depicted in Fig. 3. The necessity of the SUB space can be suggested by the clients in the beginning either by their preference or by technical or performing issues. By adding a SUB to a MAIN, a general, non-rectangular shape can be generated. This irregular shape will add more complexity in determining the layout of two neighboring spaces.

Fig. 3
figure 3

Definition of MAIN and SUB elements

Full size image

Considering a general shape generated by MAIN and SUB spaces is not straightforward. Instead of allowing impractical SUB shapes that are either too slender or too fat, SUBs with a reasonable shape factor defined, g Shape as a ratio width to length of SUB is introduced in Eq. (4). This assumption is very plausible and can be adopted without loss of generality.

$$ g_{\text{Shape}} = \frac{\text{width (SUB)}}{\text{length (SUB)}} .$$
(4)

Another simplification is assumed in positioning SUBs. Even though a SUB can be floating along an edge of a connected MAIN, the resulting shape of combined MAIN and SUB can be impractical in most cases in that the SUB could create unusable spaces for the neighboring space. This dilemma is solved by assuming the position of the SUB fixated at either the top or bottom of a MAIN. In other words, the top edge of SUB is aligned with that of MAIN or the bottom edge of SUB with that of MAIN. Using a penalty method in the fitness function, an impractical shape can be easily discarded after each generation during the CBGA process.

Another constraint considered in the space arrangement on decks is the stair connectivity. Stairs connect spaces or compartments across decks. Some stairs should be located within specified spaces for technical and operational purpose. Private stairs are preferred for guests as well as the owner, reducing the likelihood of encountering the crew more than necessary. With all these constraint factors in mind, our goal is to find an optimal arrangement of stairs that enables the shortest connection from space to space across decks.

In summary, the constraints considered in the problem are g Shape and g(x) functions. The role of g(x)s is to avoid the violation of technical requirements or user’s preference by imposing penalties. When the space is encoded into a chromosome, those constraints are evaluated by the corner positions of each space that are expressed in terms of (x, y) coordinates (Table 1).

Table 1 List of constraints g(x)
Full size table

The information of initial space connection is given in the first step. Even though the number of guest and crew stairs can be generally arbitrary, the CBGA will generate the number of stairs based on the connection from space to space following the initial recommendation. Our assumption for the initial layout is described in Fig. 4.

Fig. 4
figure 4

Initial layout of stairs

Full size image

3.2 Encoding and selection process

The proposed CBGA uses the string of x–y coordinates as variables. A set of x–y coordinates in this chromosome is exchanged during the CBGA mechanism to generate a new chromosome in next generation. Three major elements such as MAINs, SUBs, and stairs encoded to form chromosomes are illustrated in Fig. 5.

Fig. 5
figure 5

Encoding process for MAINs, SUBs, and stairs

Full size image

The steady-state selection is known to be the generic method of selection of chromosomes [10]. Each chromosome in the population has a fitness value and the whole chromosomes are sorted in terms of the fitness value from lowest to highest. Some of the lower chromosomes need replacement with better ones. The purpose of the replacement, called reproduction, is to improve the quality of current chromosomes that will become the components of the next population, expecting the forthcoming individuals achieve the higher fitness values. This replacement and deletion strategy is more practical than others because some characters of good individuals are preserved for reproduction while they are destroyed in crossover or mutation processes.

The question here is how many of the current chromosomes are to be replaced. From our experiment graphed in Fig. 6, the reproduction rate of 90 %, which means 10 % dropout, shows the best performance. This trend was also observed in our previous application of the ship hull fairing process [11]. Therefore, at a stage,10 % of the population are dropped out to discard the worst individuals and the vacancy is replaced by the new offspring that are regenerated from the 90 % that survived at that stage.

Fig. 6
figure 6

Convergence results for different reproduction percentages

Full size image

3.3 Probabilities of crossover and mutation

The efficiency of the CBGA in general depends on the population size, crossover rate, and mutation rate. The probabilities of crossover and mutation should be changed at each generation to guarantee diversity and to speed up the convergence rate in an efficient manner.

In our practice, the crossover probability p c and the mutation probability p m are adaptively applied in response to the fitness value for every individual in the population. If the values of p c and p m are greater than the default rate, crossover and mutation processes occur, respectively. The values of p c and p m are documented in Srinivas and Patnaik [12], shown in Eq. (5):

$$ p_{\text{c}} = \frac{{(f^{\prime} - f_{\min } )}}{{(f_{\text{avg}} - f_{\min } )}}\quad {\text{and}}\quad p_{\text{m}} = \frac{{(f - f_{\min } )}}{{(f_{\text{avg}} - f_{\min } )}}, $$
(5)

where f′ is the smaller fitness value of the individuals to be crossed in crossover process, f the fitness value in mutation process, and f min and f avg the minimum and average fitness values of the population, respectively. According to the formulations, p c and p m automatically increase when the solution gets stuck at a local optimum or decrease when the solution scatters in the population.

3.4 Crossover process

The idea of crossover is to exchange the "parent" chromosomes in the population to generate the two new"child" chromosomes in the next population. The examples of crossover for the three major components used in the space arrangement are depicted in Fig. 7.

Fig. 7
figure 7

Crossover process for three major components

Full size image

Our crossover with probability approaches to real value of crossover based on the lower and upper bounds of (x, y) components. These bounds can be practically described as the borders (walls) between spaces in the space arrangement problem.

It is possible that crossover operation is not feasible owing to the space restriction in our problem. For example, after a crossover operation, compartments may be overlapped to each other. As shown in Fig. 8, the MAIN space of i-th individual is successfully transferred to j-th, but the other way is not feasible. If that happens, the fitness function gets a penalty. As a result, only the individuals without penalty will be allowed for mutation. Otherwise, other "parent" individuals will be selected to regenerate the acceptable "child"individuals. This mechanism is described in Fig. 9.

Fig. 8
figure 8

Overlap constraint in crossover process

Full size image
Fig. 9
figure 9

The mechanism of crossover

Full size image

3.5 Mutation process

Mutation is an exploitation creating a deviation from a regular population. The role of mutation in the CBGA has been considered to prevent the premature convergence of a solution.

In the mutation process with probability, the position of a stair and the shape of a space are subject to change by moving, adding, or subtracting some rows and/or columns of grids, as shown in Fig. 10. Considering that the large change in the mutation step has seriously affected the convergence [11], we recommend that the numbers of changed grids, δx and δy, be less than 5 % of the total grids in the longitudinal and vertical directions, respectively, to reduce the chance of possible divergence. Then, the new design variables are expressed in term of δx and δy, as given by Eq. (6).

$$ [x_{\text{new}} ] = [x] \pm \delta x\quad {\text{and}}\quad \, [y_{\text{new}} ] = [y] \pm \delta y $$
(6)
Fig. 10
figure 10

Mutation processes

Full size image

3.6 Proposed CBGA summarized

Figure 11 illustrates the flowchart of the CBGA technique for the space arrangement process. Each step is self-explanatory.

Fig. 11
figure 11

Flowchart of proposed CBGA

Full size image

4 Application examples

In order to demonstrate the proposed algorithm, an interior design of a mid-size superyacht is examined. Four examples from a simple case where only rectangular shaped spaces are considered to a complicated combination of all objective functions are extensively investigated. The GA process implemented in this work was written in C++ and has shown to converge rapidly in most cases.

4.1 Space occupancy for simple rectangular compartments

As a starting example, a simple case where the space occupancy is solely considered is examined. The shapes of all spaces or compartments are assumed to be rectangular to make the problem simpler. This problem has a single objective function that is supposed to satisfy the area requirement defined by the designer.

The result depicted in Fig. 12 shows a good arrangement following the area requirement. Figure 13, where the x-axis is the number of generation and y-axis the fitness value, demonstrates that the given problem rapidly converges. Technically, the solution of this simple problem depends on the range of each area requirement. The solution would become unique if the upper and lower bounds of areas were sufficiently close. The fitness values obtained over generations are listed in Table 2.

Fig. 12
figure 12

Space arrangement for requirement of occupancy only (initial and final)

Full size image
Fig. 13
figure 13

Convergence of fitness value of space occupancy only over generations

Full size image
Table 2 Fitness values for space occupancy
Full size table

4.2 Space occupancy with SUB elements

Quite a number of existing superyachts possess non-rectangular compartments commonly used to represent crew space, galley, and lobby. A non-rectangular shape considered as an additional space attached to a compartment was defined as a SUB. Taking care of SUBs in the algorithm requires the higher value of the corresponding weighting factor and naturally increases the computing time. Figure 14 displays the initial and final arrangement of given spaces and the convergence rate is graphed in Fig. 15.

Fig. 14
figure 14

Space arrangement with SUB requirement (initial and final)

Full size image
Fig. 15
figure 15

Convergence of fitness value of SUB implementation over generations

Full size image

4.3 Shortest stair passage

The stair connectivity between spaces is also an important design factor. In this example, the shortest connection between stairs among crew space, galley, lobby, and fly bridge is selected as an objective function. This specific stair connectivity is intentionally made up for the test of the proposed algorithm and, thus, any combination from the user is possible. The result is shown in Fig. 16 and its convergence graph in Fig. 17. The dark square marker and the corresponding light maker on the neighboring deck form a pair, representing the starting and ending stair positions.

Fig. 16
figure 16

Space arrangement for requirement of shortest stair connection (initial and final)

Full size image
Fig. 17
figure 17

Convergence of fitness value of stair distance over generations

Full size image

4.4 Integrated objective function with stair constraint

A mid-sized superyacht with four decks containing typical inner spaces with stair constraints is chosen to incorporate all possible constraints suggested in this work. The objective functions considered in this integrated condition include the space occupancy by the area range, the existence of SUBs, and six guest stairs, and three crew stairs with the shortest connection. SUBs are assigned to crew space, galley, and lobby for a practical design. The designer or the client, however, is allowed to change these options at any time.

The initial and final space layouts are shown in Fig. 18. Figure 19 shows the converging rate of the fitness value. The final value after 100 generations converges to a very small number that clearly states that the algorithm yields a good space arrangement balancing the given constraints. The fitness value decreases rapidly within the first 20th generations because the initial space arrangement is usually regarded as a poor quality. After the 20th, minor tuning process becomes dominant.

Fig. 18
figure 18

Space arrangement for requirement of integrated objective functions (initial and final)

Full size image
Fig. 19
figure 19

Convergence of fitness value of integrated CBGA over generations

Full size image

4.5 Comparison of four test cases

The four cases are compared in Table 3. The simple requirement with space occupancy only gives the best convergence result because of its simplicity. When the other factors such as SUBs or stair connection are considered as additional fitness values, the result is in general a set of various feasible solutions because of the indeterministic property of the given requirements. Obviously, the solution based on the CBGA is not necessarily the best if each design factor is treated separately. The tendency of the resulting solution depends on the weighting values assigned.

Table 3 Comparison of four test cases
Full size table

5 Conclusions

A constraint-based genetic algorithm was developed to determine the interior space arrangement of midsized superyachts. The designer is able to generate an arrangement by assigning his or her design requirements or constraints. Three major elements, such as space, shape, and stair, were combined to set up an integrated formulation in form of a weighted sum of three elements. To solve the optimization problem, the genetic algorithm was adopted. Important design requirements or variables are converted into numerical values that can be utilized as constraints in the optimization problem.

The aim of the work is to suggest a set of probable and reasonable space arrangements that can be rapidly generated and let the expert decide a final solution through a so-called tuning process. Future work should consider the efficient manipulation of weighting factors in treating the assigned design variables. Thorough investigation on the objective function of stairs is recommended as well.